Heaps Priority Queues Building a heap BUILD-MAX-HEAP(Input_numbers) 1 Copy Input numbers to a heap 3 MAX-HEAPIFY(A O(n) note that n/2 the elements are leaf nodes Casual illustration for a Com plete-binary tree A complete- binary tree of height h has h+1 levels: 0, 1, 2, 3,h The levels have 20, 21, 22, 23, .2h elements respectively Then maximum total no of float down" carried out by maX-HeaPify sum of maximum no of"float down"of all non-leaf nodes(levels h-1, h-2, ..O =1X2h1+2x2h2+3X2h3+4x2h4+hX20 =2(1/2+214+38+416.) [note: 2+1=n+1, thus 2 =0.5*(n+1) 0.5(n+1)(12+24+3/8+4/16.)[note:12+2/4+3/8+4/16.<2] 0.5(+1)*2=(n+1) o(n) CS3381 Des Anal of Alg(2001-2002 SemA) Continue City Univ of HK /Dept of CS Helena Wong http://www.cs.cityu.edu.hk/-helena 6. Graph Algorithms-6
CS3381 Des & Anal of Alg (2001-2002 SemA) City Univ of HK / Dept of CS / Helena Wong http://www.cs.cityu.edu.hk/~helena 6. Graph Algorithms - 6 Heaps & Priority Queues BUILD-MAX-HEAP(Input_numbers) 1 Copy Input_numbers to a heap 2 For i = n/2 down to 1 /*all non-leaf nodes */ 3 MAX-HEAPIFY(A,i) Building a heap: 1 2 3 4 5 6 7 8 9 10 .. .. 11 14 15 Note that n/2the elements are leaf nodes 1 2 3 4 5 6 7 8 9 10 Casual illustration for a Complete-binary tree: A complete-binary tree of height h has h+1 levels: 0,1,2,3,.. h. The levels have 20 ,21 ,22 ,23 ,…2h elements respectively. Then, maximum total no. of “float down” carried out by MAX-HEAPIFY = sum of maximum no. of “float down” of all non-leaf nodes (levels h-1, h-2, .. 0) = 1 x 2h-1 + 2 x 2h-2 + 3 x 2h-3 + 4 x 2h-4 + .. h x 20 = 2h (1/2 + 2/4 + 3/8 + 4/16…) [note: 2h+1 = n+1, thus 2h=0.5*(n+1)] = 0.5(n+1) (1/2 + 2/4 + 3/8 + 4/16…) [note: 1/2 + 2/4 + 3/8 + 4/16.. <2] < 0.5(n+1) * 2 = (n+1) = O(n) O(n) Show Summation Continue
lllustration:1/2+214+3/{8+4/16..<2 12 =0.5 Return 1/2+24 1/2+24+3/8 1375 1/2+24+3/8+4/16 =1625 1/2+24+3/8+4/16+5/32 =178125 1/2+24+3/8+416+5/32+6/64 =1875 1/2+24+318+4/16+532+6/64+7/128 =19296875 1/2+24+318+4/16+532+6/64+7/128+8/256 =19609375 1/2+24+318+4/16+532+6/64+7/128+8/256+9/512 1978515625 1/2+24+38+4/16+5/32+664+7/128+8/256+9512+10/1024 =198828125 1/2+24+3/8+416+5/32+6/64+7/128+8/256+9/512+10/1024+112048=1993652344 CS3381 Des Anal of Alg(2001-2002 SemA) City Univ of HK /Dept of CS /Helena Wong http://www.cs.cityu.edu.hk/-helena 6. Graph Algorithms-7
CS3381 Des & Anal of Alg (2001-2002 SemA) City Univ of HK / Dept of CS / Helena Wong http://www.cs.cityu.edu.hk/~helena 6. Graph Algorithms - 7 Illustration: 1/2 + 2/4 + 3/8 + 4/16.. <2 1/2 = 0.5 1/2+2/4 = 1 1/2+2/4+3/8 = 1.375 1/2+2/4+3/8+4/16 = 1.625 1/2+2/4+3/8+4/16+5/32 = 1.78125 1/2+2/4+3/8+4/16+5/32+6/64 = 1.875 1/2+2/4+3/8+4/16+5/32+6/64+7/128 = 1.9296875 1/2+2/4+3/8+4/16+5/32+6/64+7/128+8/256 = 1.9609375 1/2+2/4+3/8+4/16+5/32+6/64+7/128+8/256+9/512 = 1.978515625 1/2+2/4+3/8+4/16+5/32+6/64+7/128+8/256+9/512+10/1024 = 1.98828125 1/2+2/4+3/8+4/16+5/32+6/64+7/128+8/256+9/512+10/1024+11/2048 = 1.993652344 Return
Heaps Priority Queues Priority queue 9 Is a data structure for maintaining a set of elements each associated with a key e Maximum priority queue supports the following operations INSERT(S, x) Insert element x into the set s MAXIMUM(S Return the 'largest element EXTRACT-MAX(S)-Remove and return the 'largest element INCREASE-KEY(S, x,v)-Increase x's key to a new value, V We can implement priority queues based on a heap structure CS3381 Des Anal of Alg(2001-2002 SemA) City Univ of HK /Dept of CS Helena Wong http://www.cs.cityu.edu.hk/-helena 6. Graph Algorithms-8
CS3381 Des & Anal of Alg (2001-2002 SemA) City Univ of HK / Dept of CS / Helena Wong http://www.cs.cityu.edu.hk/~helena 6. Graph Algorithms - 8 Heaps & Priority Queues Priority queue Is a data structure for maintaining a set of elements each associated with a key. Maximum priority queue supports the following operations: INSERT(S,x) - Insert element x into the set S MAXIMUM(S) - Return the ‘largest’ element EXTRACT-MAX(S) - Remove and return the ‘largest’ element INCREASE-KEY(S,x,v) - Increase x’s key to a new value, v We can implement priority queues based on a heap structure
Heaps Priority Queues MAXIMUM(A) 1 return A[1] ⊙(1) ②2④① HEAP-EXTRACT-MAX(A) o( 16 234567 ⑦ ⑦(9)(③3) ②④④ Step 1. save the value of the root that is to be returned Step 2. Move the last value to the root node Step 3. MAX-HEAPIFY(A, 1/ the root node*) CS3381 Des Anal of Alg(2001-2002 SemA) City Univ of HK /Dept of CS Helena Wong http://www.cs.cityu.edu.hk-helena 6. Graph Algorithms-9
CS3381 Des & Anal of Alg (2001-2002 SemA) City Univ of HK / Dept of CS / Helena Wong http://www.cs.cityu.edu.hk/~helena 6. Graph Algorithms - 9 HEAP-EXTRACT-MAX(A) 1 2 3 4 5 6 7 Step 1. Save the value of the root that is to be returned. Step 2. Move the last value to the root node. Step 3. MAX-HEAPIFY(A,1/*the root node*/). Heaps & Priority Queues MAXIMUM(A) 1 return A[1] 16 14 10 8 7 9 3 2 4 1 14 10 8 7 9 3 2 4 1 16 1 14 10 8 7 9 3 2 4 14 8 10 4 7 9 3 2 1 (1) O(lg n)
Heaps Priority Queues HEAP-INCREASE-KEY(A, v) o(lg n) 40 16 3 Increase 58⑦⑨③ 0⑩ 0④④ 8④④ ⑧④④ Keep on exchanging with parent until parent is greater than the current node o(g n) MAX-HEAP-INSERT(A, key) 1n=n+1 ⑩ 2A]=-0 3 HEAP-INCREASE-KEY(A, n, key②④④ ②④⑩ CS3381 Des Anal of Alg(2001-2002 SemA) City Univ of HK /Dept of CS Helena Wong http://www.cs.cityu.edu.hk/-helena 6. Graph Algorithms-10
CS3381 Des & Anal of Alg (2001-2002 SemA) City Univ of HK / Dept of CS / Helena Wong http://www.cs.cityu.edu.hk/~helena 6. Graph Algorithms - 10 Heaps & Priority Queues HEAP-INCREASE-KEY(A,i,v) 1 2 3 4 5 6 MAX-HEAP-INSERT(A,key) 1 n = n+1 2 A[n]= - 3 HEAP-INCREASE-KEY(A,n,key) 16 14 10 8 7 9 3 2 4 1 Increase to 15 16 14 10 8 7 9 3 15 4 1 16 14 10 15 7 9 3 8 4 1 16 15 10 14 7 9 3 8 4 1 Keep on exchanging with parent until parent is greater than the current node. O(lg n) 16 14 10 8 7 9 3 2 4 1 - 16 14 10 8 7 9 3 2 4 115 … O(lg n)