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