Heap Sort

of 13
4 views
PDF
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Document Description
9/26/2011 Heap Sort Heap Sort The binary heap data structures is an array that can be viewed as a complete binary tree. Each node of the binary tree corresponds to an element of the array. The array is completely filled on all levels except possibly lowest. We represent heaps in level order, going from left to right. The array corresponding to the heap above is [25, 13, 17, 5, 8, 3]. The root of the tree A[1] and given index i of a node, the indices of its parent, left child and right child
Document Share
Document Tags
Document Transcript
  Heap Sort   The binary heap data structures is an array that can be viewed as a complete binary tree.Each node of the binary tree corresponds to an element of the array. The array is completelyfilled on all levels except possibly lowest.   We represent heaps in level order, going from left to right. The array corresponding to theheap above is [25, 13, 17, 5, 8, 3].   The root of the tree A[1] and given index i of a node, the indices of its parent, left child andright child can be computed  PARENT ( i )return floor( i /2  LEFT ( i )return 2 i RIGHT ( i )return 2 i + 1   Let's try these out on a heap to make sure we believe they are correct. Take this heap, 9/26/2011 Heap Sortwww.personal.kent.edu/…/heapSort.htm 1/13  which is represented by the array [20, 14, 17, 8, 6, 9, 4, 1].We'll go from the 20 to the 6 first. The index of the 20 is 1. To find the index of the left child,we calculate 1 * 2 = 2. This takes us (correctly) to the 14. Now, we go right, so we calculate2 * 2 + 1 = 5. This takes us (again, correctly) to the 6. Now let's try going from the 4 to the 20. 4's index is 7. We want to go to the parent, so wecalculate 7 / 2 = 3, which takes us to the 17. Now, to get 17's parent, we calculate 3 / 2 = 1,which takes us to the 20.   Heap Property In a heap, for every node i other than the root, the value of a node is greater than or equal (atmost) to the value of its parent.  A[PARENT ( i )] ≥  A[ i ] Thus, the largest element in a heap is stored at the root.   Following is an example of Heap: 9/26/2011 Heap Sortwww.personal.kent.edu/…/heapSort.htm 2/13    By thedefinition of a heap, all the tree levels are completely filled except possibly for thelowest level, which is filled from the left up to a point. Clearly a heap of height h has theminimum number of elements when it has just one node at the lowest level. The levels abovethe lowest level form a complete binary tree of height h -1 and 2 h -1 nodes. Hence theminimum number of nodes possible in a heap of height h is 2 h . Clearly a heap of height h ,has the maximum number of elements when its lowest level is completely filled. In this casethe heap is a complete binary tree of height h and hence has 2 h+1 -1 nodes.Following isnot a heap, because it only has the heap property - it is not a complete binarytree. Recall that to be complete, a binary tree has to fill up all of its levels with the possibleexception of the last one, which must be filled in from the left side.   Height of a node We define the height of a node in a tree to be a number of edges on the longest simpledownward path from a node to a leaf.   Height of a tree The number of edges on a simple downward path from a root to a leaf. Note that the heightof a tree with n node is lg n which is ( lg n ). This implies that an n-element heap hasheight lg n In order to show this let the height of the n -element heap be h . From the bounds obtained on 9/26/2011 Heap Sortwww.personal.kent.edu/…/heapSort.htm 3/13  maximum and minimum number of elements in a heap, we get 2 h ≤ n ≤ 2 h+1 -1 Where n is the number of elements in a heap. 2 h ≤ n ≤ 2 h+1 Taking logarithms to the base 2 h ≤ lg n ≤ h +1 It follows that h = lg n    We known from above that largest element resides in root, A[1] . The natural question to ask is where in a heap might the smallest element resides? Consider any path from root of the treeto a leaf. Because of the heap property, as we follow that path, the elements are either decreasing or staying the same. If it happens to be the case that all elements in the heap aredistinct, then the above implies that the smallest is in a leaf of the tree. It could also be that anentire subtree of the heap is the smallest element or indeed that there is only one element inthe heap, which in the smallest element, so the smallest element is everywhere. Note thatanything below the smallest element must equal the smallest element, so in general, only entiresubtrees of the heap can contain the smallest element.   Inserting Element in the Heap   Suppose we have a heap as follows 9/26/2011 Heap Sortwww.personal.kent.edu/…/heapSort.htm 4/13
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks
SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...

Sign Now!

We are very appreciated for your Prompt Action!

x