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-6CS3381 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/2the 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