Lecture Notes CMSC 251 A heap is represented as an left complete binary tree This means that all the levels of the tree are full except the bottommost level which is filled from left to right An example is shown below The keys of a heap are stored in something called heap order This means that for each node u other than the root key Parent u key u This implies that as you follow any path from a leaf to the root the keys appear in nonstrict increasing order Notice that this implies that the root is necessarily the largest element 16 14 10 8 2 Left complete Binary Tree 7 4 9 3 1 Heap ordering Figure 11 Heap Next time we will show how the priority queue operations are implemented for a heap Lecture 13 HeapSort Tuesday Mar 10 1998 Read Chapt 7 in CLR Heaps Recall that a heap is a data structure that supports the main priority queue operations insert and extract max in log n time each It consists of a left complete binary tree meaning that all levels of the tree except possibly the bottommost are full and the bottommost level is filled from left to right As a consequence it follows that the depth of the tree is log n where n is the number of elements stored in the tree The keys of the heap are stored in the tree in what is called heap order This means that for each nonroot node its parent s key is at least as large as its key From this it follows that the largest key in the heap appears at the root Array Storage Last time we mentioned that one of the clever aspects of heaps is that they can be stored in arrays without the need for using pointers as would normally be needed for storing binary trees The reason for this is the left complete nature of the tree This is done by storing the heap in an array A 1 n Generally we will not be using all of the array since only a portion of the keys may be part of the current heap For this reason we maintain a variable m n which keeps track of the current number of elements that are actually stored actively in the heap Thus the heap will consist of the elements stored in elements A 1 m We store the heap in the array by simply unraveling it level by level Because the binary tree is leftcomplete we know exactly how many elements each level will supply The root level supplies 1 node the next level 2 then 4 then 8 and so on Only the bottommost level may supply fewer than the appropriate power of 2 but then we can use the value of m to determine where the last element is This is illustrated below We should emphasize that this only works because the tree is left complete This cannot be used for general trees 41 Lecture Notes CMSC 251 16 1 1 2 14 4 8 2 10 3 8 7 4 9 1 5 6 3 9 2 3 4 5 6 7 8 9 10 11 12 13 16 14 10 8 7 9 3 2 4 1 7 m 10 n 13 10 Heap as a binary tree Heap as an array Figure 12 Storing a heap in an array We claim that to access elements of the heap involves simple arithmetic operations on the array indices In particular it is easy to see the following Left i return 2i Right i return 2i 1 Parent i return bi 2c IsLeaf i return Left i m That is if i s left child is not in the tree IsRoot i return i 1 For example the heap ordering property can be stated as for all i 1 i n if not IsRoot i then A Parent i A i So is a heap a binary tree or an array The answer is that from a conceptual standpoint it is a binary tree However it is implemented typically as an array for space efficiency Maintaining the Heap Property There is one principal operation for maintaining the heap property It is called Heapify In other books it is sometimes called sifting down The idea is that we are given an element of the heap which we suspect may not be in valid heap order but we assume that all of other the elements in the subtree rooted at this element are in heap order In particular this root element may be too small To fix this we sift it down the tree by swapping it with one of its children Which child We should take the larger of the two children to satisfy the heap ordering property This continues recursively until the element is either larger than both its children or until its falls all the way to the leaf level Here is the pseudocode It is given the heap in the array A and the index i of the suspected element and m the current active size of the heap The element A max is set to the maximum of A i and it two children If max 6 i then we swap A i and A max and then recurse on A max Heapify Heapify array A int i int m l Left i r Right i max i if l m and A l A max max l if r m and A r A max max r if max i swap A i with A max Heapify A max m 42 sift down A i in A 1 m left child right child left child exists and larger right child exists and larger if either child larger swap with larger child and recurse Lecture Notes CMSC 251 See Figure 7 2 on page 143 of CLR for an example of how Heapify works in the case where m 10 We show the execution on a tree rather than on the array representation since this is the most natural way to conceptualize the heap You might try simulating this same algorithm on the array to see how it works at a finer details Note that the recursive implementation of Heapify is not the most efficient We have done so because many algorithms on trees are most naturally implemented using recursion so it is nice to practice this here It is possible to write the procedure iteratively This is left as an exercise The HeapSort algorithm will consist of two major parts First building a heap and then extracting the maximum elements from the heap one by one We will see how to use Heapify to help us do both of these How long does Hepify take to run Observe that we perform a constant amount of work at each level of the tree until we make a call to Heapify at the next lower level of the tree Thus we do O 1 work for each level of the tree which we visit Since there are log n levels altogether in the tree the total …