• Always keep the thing we are most interested in close to the top (and fast to access).
• Like a binary search tree, but less structured.
• No relationship between keys at the same level (unlike BST).
What is a heap?
Types of heaps
• Min heap: priority 1 more important than 100
• Max heap: 100 more important than 1 – We are going to talk about max heaps.
• Maxheap-orderproperty
– Look at any node u, and its parent p. – p.priority ≥ u.priority
p:7
u:3
Abstract data type (ADT)
• We are going to use max-heaps to implement the
(max) priority queue ADT
• A priority queue Q offers (at least) 2 operations: – Extract-max(Q): returns the highest priority element – Insert(Q, e): inserts e into Q
• Every time an Insert or Extract-max changes the heap, it must restore the max-heap order property. (Prove by induction on the sequence of inserts and extract-maxes that occur.)
What can we do with a heap
• Can do same stuff with a BST… why use a heap?
– BST extract-max is O(depth); heap is O(log n)! • When would we use a BST?
– When we need to search for a particular key.
Storing a heap in memory • Heaps are typically implemented with arrays.
• Thearrayisjustalevel-ordertraversaloftheheap.
• Thechildrenofthenodeatindexiareat2iand2i+1.
Example time
• Interactive heap visualization
• Insert places a key in a new node that is the
last node in a level-order-traversal of the heap. • The inserted key is then “bubbled” upwards until
the heap property is satisfied.
• Extract-max removes the last node in a level- order-traversal and moves its key into the root.
• The new key at the root is then bubbled down until the heap property is satisfied.
• Bubbling down is also called heapifying.
Building a max-heap in O(n) time
• Suppose we want to build a heap from an unsorted array: 10, 2, 7, 8, 6, 5, 9, 4, 3, 11.
• We start by interpreting the array as a tree.
Building a heap: a helper function
Precondition: trees rooted at L and R are heaps Postcondition: tree rooted at I is a heap
I:3
MaxHeapify(A,I): L = LEFT(I)
R = RIGHT(I)
If L ≤ heap_size(A) and A[L] > A[I] then max = L
else max = I
Case 2: max = I Heap OK!
L:3
R:5
If R ≤ heap_size(A) and A[R] > A[max] then max = R
I:5
If max is L or R then swap(A[I],A[max]) MaxHeapify(A,max)
Case 3: max = R Need to fix… L:3
R:7
Case 1: max = L Need to fix…
L:7
R:5
I:7
Proving MaxHeapify is correct
• How would you formally prove that MaxHeapify is correct?
• Goal: Prove MaxHeapify is correct for all inputs.
“Correct” means: “if the precondition is satisfied when MaxHeapify is called, then the postcondition will be satisfied when it finishes.”
• How do we prove a recursive function correct?
– Define a problem size, and prove correctness by induction on
problem size.
– Base case: show function is correct for any input of the smallest problem size.
– Inductive step: assume function is correct for problem size j; show it is correct for problem size j+1.
Proving MaxHeapify is correct – 2
• Let’sapplythistoMaxHeapify.
• Problemsize:heightofnodeI.
• Basecase:ProveMaxHeapifyiscorrectforeveryinput with height(I) = 0.
• Inductivestep:LetAandIbeanyinputparametersthat satisfy the precondition.
Assume MaxHeapify is correct when the problem size is j. Prove MaxHeapify is correct when the problem size is j+1.
Proving MaxHeapify is correct – 3
Precondition: trees rooted at L and R are heaps Postcondition: tree rooted at I is a heap
I:3
MaxHeapify(A,I): L = LEFT(I)
R = RIGHT(I)
If L ≤ heap_size(A) and A[L] > A[I] then max = L
else max = I
Case 2: max = I Heap OK!
L:3
R:5
If R ≤ heap_size(A) and A[R] > A[max] then max = R
I:5
If max is L or R then swap(A[I],A[max]) MaxHeapify(A,max)
Case 3: max = R Need to fix… L:3
R:7
Case 1: max = L Need to fix…
L:7
R:5
I:7
The main function
BUILD-MAX-HEAP(A):
for i = heap_size(A)/2 down to 1
MaxHeapify(A,i)
Analyzing worst-case complexity
Analyzing worst-case complexity
• ≤ 2d nodes at depth d
• Node at depth d has height ≤ h-d
• Cost to “heapify” one node at depth d is ≤ c(h-d) – Don’t care about constants… Ignoring them below…
• Cost to heapify all nodes at depth d is ≤ 2d (h-d)
• So, cost to heapify all nodes over all depths is: