Heaps Priority Queues Maximum No of elements Maximum no of elements a one-level tree(height=0) level 0 a 2-level tree(height=1): 3 level 1 2 level 2 a 3-level tree (height=2): 7 level 3 8{8 a 4-level tree(height=3 15 Therefore, for a heap containing n elements Maximum no of elements in level k =2k Height of tree =LIg n ]=O(lg n) Basic procedures: MAX-HEAPIFY o(g n) HEAP-EXTRACT-MAX O(g n) BUILD-MAX-HEAP O(n) HEAP-INCREASE-KEY O(g n) MAX-HEAP-INSERT O(g n) HEAP-MAXIMUM o(g n) 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-5CS3381 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 - 5 Heaps & Priority Queues Basic procedures: MAX-HEAPIFY O(lg n) BUILD-MAX-HEAP O(n) MAX-HEAP-INSERT O(lg n) Maximum No. of elements Maximum No. of elements Therefore, for a heap containing n elements : a one-level tree (height=0): 1 1 2 3 4 5 6 7 8 9 10 Maximum no. of elements in level k = 2 Height of tree = lg n  = (lg n) k HEAP-EXTRACT-MAX O(lg n) HEAP-INCREASE-KEY O(lg n) HEAP-MAXIMUM O(lg n) a 2-level tree (height=1): 3 a 3-level tree (height=2): 7 a 4-level tree (height=3): 15 level 0: 1 level 1: 2 level 2: 4 level 3: 8