Heaps Priority Queues MAX-HEAPIFY(A, i The binary trees rooted at LEFT( and RIGHT( are max-heaps 234 But A[] may be smaller than its children MAX-HEAPlFY is to"float down"[]to o(height of node i) make the subtree rooted at A[i] a max-heap. =Olg n) 9)(3 ⑦9(3 8 9)(3 2)(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-4CS3381 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 - 4 Heaps & Priority Queues MAX-HEAPIFY(A,i) 1 2 3 4 .. The binary trees rooted at LEFT(i) and RIGHT(i) are max-heaps But A[i] may be smaller than its children. MAX-HEAPIFY is to “float down” A[i] to make the subtree rooted at A[i] a max-heap. 16 4 10 14 7 9 3 2 8 1 1 i=2 3 4 5 6 7 8 9 10 16 14 10 4 7 9 3 2 8 1 1 2 3 i=4 5 6 7 8 9 10 16 14 10 8 7 9 3 2 4 1 1 2 3 4 5 6 7 8 i=910 O(height of node i) = O(lg n)