COMP 250
INTRODUCTION TO COMPUTER SCIENCE
Week 12-3 : Heaps
Giulia Alberini, Fall 2020 Slides adapted from Michael Langer’s
WHAT ARE WE GOING TO DO IN THIS VIDEO?
How to build a heap naively: best and worst case write removeMin() using array indices
Faster algorithm for building a heap
BUILD A HEAP
HOW TO BUILD A HEAP?
Suppose we have a list with 𝑛 elements, we can create an empty heap and use add() to add one element at a time to the heap:
buildHeap(list){
create new heap array // capacity > list.size() for (k = 0; k < list.size(); k++)
add( list[k] ) // add the element to the heap }
Note that you could write the buildHeap algorithm slightly differently by putting all the list elements into the array at the beginning, and then `upheaping’ each one.
BEST CASE OF BUILDHEAP IS ... ?
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Suppose we want to add some elements to an empty heap:
acbelukmf
How many swaps do we need to add each element? In the best case, ...
BESTCASEOFBUILDHEAP IS 𝑶(𝒏)
a
c
b
e
l
u
k
m
f
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Suppose we want to add some elements to an empty heap:
acbelukmf
How many swaps do we need to add each element?
In the best case, the order of elements that we add is already a heap, and no swaps are necessary.
WORST CASE OF BUILDHEAP IS ... ?
f 4a5e6 7
level
0 1
2 3
1 2c3
8
9 10 11 12 13
How many swaps do we need to add the 𝑖-th element?
WORST CASE OF BUILDHEAP IS ... ?
f 4a5e6 7
level
0 1
2 3
1 2c3
8
9 10 11 12 13
How many swaps do we need to add the 𝑖-th element? Element 𝑖 gets added to some 𝑙𝑒𝑣𝑒𝑙, such that:
2𝑙𝑒𝑣𝑒𝑙 ≤ 𝑖 < 2𝑙𝑒𝑣𝑒𝑙 +1
WORST CASE OF BUILDHEAP IS ... ?
f 4a5e6 7
level
0 1
2 3
1 2c3
8
9 10 11 12 13
2𝑙𝑒𝑣𝑒𝑙 ≤ 𝑖 < 2𝑙𝑒𝑣𝑒𝑙 +1 𝑙𝑒𝑣𝑒𝑙 ≤ log2𝑖 < 𝑙𝑒𝑣𝑒𝑙+1
Thus, 𝑙𝑒𝑣𝑒𝑙 = 𝑓𝑙𝑜𝑜𝑟(log2 𝑖)
WORST CASE OF BUILDHEAP IS ... ?
f 4a5e6 7
level
0 1
2 3
1 2c3
8
9 10 11 12 13
Suppose there are 𝑛 elements to add, then in the worst case the number of swaps needed to add all the elements is:
𝑛
𝑡 𝑛 = 𝑓𝑙𝑜𝑜𝑟(log2 𝑖) 𝑖=1
12
𝑙𝑜𝑔2 𝑖
8
4
0
𝑓𝑙𝑜𝑜𝑟( 𝑙𝑜𝑔2 𝑖 )
0
1000 2000
3000 4000 5000
𝑖
12
𝑙𝑜𝑔2 𝑖
8
4
0
𝑡 𝑛 =σ𝑛 𝑖=1
𝑓𝑙𝑜𝑜𝑟(𝑙𝑜𝑔 𝑖) 2
0
1000 2000
3000 4000 5000
Area under the dashed curve is the total number of swaps (worst case) of buildHeap.
𝑖
𝑙𝑜𝑔2 𝑛
𝑙𝑜𝑔2 𝑖
𝑡𝑛 ≤ 𝑛𝑙𝑜𝑔𝑛 2
8
4
0
0
1000 2000
3000 4000 n
𝑖
𝑙𝑜𝑔2 𝑛
𝑙𝑜𝑔2 𝑖
1 2
𝑛𝑙𝑜𝑔2𝑛≤ 𝑡𝑛 ≤ 𝑛𝑙𝑜𝑔2𝑛
8
4
0
0
1000 2000
3000 4000 n
𝑖
WORSTCASEOFBUILDHEAP IS 𝑶(𝒏∗𝒍𝒐𝒈 𝒏) 𝟐
f 4a5e6 7
level
0 1
2 3
1 2c3
8
9 10 11 12 13
Thus, in the worst case scenario for buildHeap() is 𝑂(𝑛 ∗ log 𝑛)
removeMin()
add()
removeMin()
“upHeap”
“downHeap”
E.G. removeMin()
1 2c3b
a
4e5l6u7k f
89
Not used
m
a
c
b
e
l
u
k
m
f
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
E.G. removeMin()
f
a
Not used
1 2c3b
4e5l6u7k m
89
f
c
b
e
l
u
k
m
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
E.G. removeMin()
b
Not used
1
2c 3f
4e5l6u7k m
89
b
c
f
e
l
u
k
m
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
REMOVEMIN() - IMPLEMENTATION
Let heap be the underlying array, and let size be the number of elements in the heap.
removeMin( ){
tmpElement = heap[1] // heap[0] not used. heap[1] = heap[size]
heap[size] = null // not necessary
return tmpElement
}
REMOVEMIN() - IMPLEMENTATION
Let heap be the underlying array, and let size be the number of elements in the heap.
removeMin( ){
tmpElement = heap[1] // heap[0] not used. heap[1] = heap[size]
heap[size] = null // not necessary
size = size – 1
downHeap(1, size)
return tmpElement
}
DOWNHEAP() - IMPLEMENTATION
downHeap( startIndex , maxIndex ){
i = startIndex
while (2*i <= maxIndex){ // if there is a left child
child = 2*i
} }
DOWNHEAP() - IMPLEMENTATION
downHeap( startIndex , maxIndex ){
i = startIndex
while (2*i <= maxIndex){ // if there is a left child
child = 2*i
if (child < maxIndex) { // if there is a right sibling
if (heap[child + 1] < heap[child]) // if rightchild < leftchild
child = child + 1
}
} }
DOWNHEAP() - IMPLEMENTATION
downHeap( startIndex , maxIndex ){
i = startIndex
while (2*i <= maxIndex){ // if there is a left child
child = 2*i
if (child < maxIndex) { // if there is a right sibling
if (heap[child + 1] < heap[child]) // if rightchild < leftchild
child = child + 1
}
if (heap[child] < heap[i]){ // Do we need to swap with child?
swapElements(i , child)
i = child
} else
break }
}
BUILD A HEAP (fast)
HOWTOBUILDAHEAP? (FAST)
f
c ae
Observations:
Half the nodes of a heap are leaves.
(Each leaf is a heap with one node)
The last non-leaf node has index size/2.
HOWTOBUILDAHEAP? (FAST)
buildHeapFast(){
// assume that heap[ ] array contains size elements for (k = size/2; k >= 1; k–)
}
downHeap( k, size )
EXAMPLE
k =3
123456 ———————- wxtprf
1w 2×3
t 4p5r6
f
EXAMPLE
k =3
123456 ———————- wxtprf
1w 2×3
4p5r6
t downHeap( 3, 6 ) f
EXAMPLE
k =3
123456 ———————- wxfprt
1w 2×3
4p5r6
f downHeap( 3, 6 ) t
EXAMPLE
123456 ———————- wxfprt
1w
downHeap( 2, 6 ) 2 x 3 f
4p5r6
k =2
t
EXAMPLE
123456 ———————- wpfxrt
1w
downHeap( 2, 6 ) 2 p 3 f
4x5r6
k =2
t
EXAMPLE
k =1
downHeap( 1, 6 ) 2p3
123456 ———————- wpfxrt
1w
f
4x5r6
t
EXAMPLE
k =1
downHeap( 1, 6 ) 2p3
123456 ———————- fpwxrt
1f
w
4x5r6
t
EXAMPLE
k =1
downHeap( 1, 6 ) 2p3
123456 ———————- fptxrw
1f
t
4x5r6
w
BUILDHEAPFAST() – IMPLEMENTATION
buildHeapFast(list){
// copy elements from list to heap array for (k = size/2; k >= 1; k–)
}
downHeap( k, size )
Claim: this algorithm is 𝑂(n).
What is the intuition for why this algorithm is so fast?
We tends to draw binary trees like this:
But the number of nodes doubles at each level. So we should draw trees like this:
height h
height h
BUILDHEAP ALGORITHMS
naive
height h
fast
Most nodes swap ~h times in worst case.
Few nodes swap ~h times in worst case.
HOW TO SHOW BUILDHEAPFAST IS 𝑶(𝒏)?
The worst case number of swaps needed to downHeap node 𝑖 is
the height of that node.
𝑡𝑛 = σ𝑛 h𝑒𝑖𝑔h𝑡𝑜𝑓𝑛𝑜𝑑𝑒𝑖
1⁄2 of the nodes do no swaps.
1⁄4 of the nodes do at most one swap. 1/8 of the nodes do at most two swaps….
𝑖=1
ASSUME THE LAST LEVEL IS FULL
height level
31f0 2231
1 4a5e6 7 2
0dddddd3 8 9 10 11 12 13 14 15
WORSECASEOFBUILDHEAPFAST ?
How many elements at 𝑙𝑒𝑣𝑒𝑙 𝑙 ? (𝑙 ∈ 0,…, h) What is the height of each 𝑙𝑒𝑣𝑒𝑙 𝑙 node?
WORSECASEOFBUILDHEAPFAST ?
How many elements at 𝑙𝑒𝑣𝑒𝑙 𝑙 ? (𝑙 ∈ 0,…, h) 2𝑙
What is the height of each 𝑙𝑒𝑣𝑒𝑙 𝑙 node? h−𝑙
𝑡 𝑛 =σ𝑛 h𝑒𝑖𝑔h𝑡𝑜𝑓𝑛𝑜𝑑𝑒𝑖 𝑖=1
=?
WORSECASEOFBUILDHEAPFAST ?
How many elements at 𝑙𝑒𝑣𝑒𝑙 𝑙 ? (𝑙 ∈ 0,…, h) 2𝑙
What is the height of each 𝑙𝑒𝑣𝑒𝑙 𝑙 node? h−𝑙
𝑡 𝑛 =σ𝑛 h𝑒𝑖𝑔h𝑡𝑜𝑓𝑛𝑜𝑑𝑒𝑖 𝑖=1
=σh h−𝑙 2𝑙 𝑙=0
Easy Difficult
(number of nodes) (sum of node levels)
(See next slide)
Since , we get :
Second term index goes to h-1 only
Since , we get :
SUMMARY: BUILDHEAPALGORITHMS
naive
fast
height h
𝑂 𝑛 𝑙𝑜𝑔2 𝑛
𝑂(𝑛)
In the next videos: Hashing
Graphs