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
The height of a heap of n elements is
Big-Theta(lg n)
The basic operations on heaps take ___ time because ___
basic heap operations take O(lg n) time because they run in time proportional to the height of the binary tree
Purpose of Max-Heapify routine
Maintains the max-heap property
Max-Heapify assumes what about the child subtrees of node i?
It assumes that Left(i) and Right(i) are max-heaps (but doesn’t know if node i is larger than its children or not)
For a heap subtree of size n, how big are the child subtrees of the root node? In what case are these child subtrees at their largest relative to the overall subtree size?
The child subtrees have at most 2n/3 nodes. The worst case (when the child subtrees are at their largest w.r.t. the parent subtree) occurs when the bottom level of the tree is exactly half full.
What recurrence describes the running time of Max-Heapify?
T(n) <= T(2n/3) + Big-Theta(1)
What is the running time of Max-Heapify in terms of the number of nodes n? In terms of the height of the tree, h?
O(lg n) or O(h)
Pseudocode for Max-Heapify
