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-9CS3381 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)