Ch6: Heaps Flashcards
Heapsort’s running time
O(n lg n)
Heapsort in-place or out-of-place?
Heapsort sorts in place
Heap data structure is also an efficient…
priority queue
(Binary) Heap data structure is…
an array object we can view as a nearly complete binary tree
How is the heap binary tree filled?
It is completely filled on all levels, except possibly the lowest, where it is filled from the left up to a point
An array object A that represents the heap has two properties: A.length is the array capacity, and…
A.heap-size represents how many array elements are active heap nodes
The root node of the heap is stored in
A[1]
Parent(i)
floor(i/2)
Left(i)
2*i
Right(i)
2*i + 1
Two kinds of binary heaps
max-heaps and min-heaps
max-heap property
For every node i other than the root, A[Parent(i)] >= A[i]
min-heap property
For every node i other than the root, A[Parent(i)] <= A[i]
The root of a max-heap is the…
largest element
The root of a min-heap is the…
smallest element