程序代写代做代考 algorithm C graph COMP 250

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