CSE310 Lecture 09 Heaps and Heapsort Guoliang Larry Xue Department of CSE Arizona State University http www fulton asu edu xue Guoliang Xue asu edu Topics of this lecture The Heap Data Structure Insertion in log time Deletion in log time Delete max in log time Build Heap in Linear Time Heapsort 2 Guoliang Xue asu edu Heaps The binary heap data structure is an array object that can be viewed as a complete binary tree Ex 1 1 20 2 18 10 4 7 12 5 6 5 4 2 1 7 8 9 10 11 12 8 3 9 7 2 3 4 5 6 7 8 9 10 11 12 20 18 10 7 12 8 9 5 4 2 1 7 heap heap viewed as a binary tree complete binary tree a binary tree that is completely filled on all levels except possibly the lowest The lowest level of a heap viewed as a binary tree is filled from left to right Guoliang Xue asu edu 3 1 1 20 2 18 10 4 7 12 5 6 5 4 2 1 7 8 9 10 11 12 8 3 9 2 3 4 5 6 7 8 9 10 11 12 20 18 10 7 12 8 9 5 4 2 1 7 7 PARENT i return i 2 parent of i in the tree LEFT i return 2i left child of i in the tree RIGHT i return 2i 1 right child of i in the tree heap property for every node i other than root A PARENT i A i 4 Guoliang Xue asu edu height of a node in a tree of edges on the longest simple downward path from the node to a leaf height of a tree is the height of its root the height of an n node complete binary tree is log n why the basic operations on heaps run in time at most proportional to its height as we will see Basic operations on a heap run in log n time Heaps are used in sorting algorithms priority queue data structure 5 Guoliang Xue asu edu Five basic procedures HEAPIFY maintains heap property O log n BUILD HEAP produces a heap from an unordered input array O n HEAPSORT sorts an array in place O n log n EXTRACT MAX and INSERT allow heap data structure to be used as a priority queue O log n Maintaining the Heap Property When heap property is violated at A i i e subtrees rooted at LEFT i and RIGHT i are heaps but A i is smaller than its children then let value of A i float down the heap 20 i 2 7 5 20 10 8 18 4 12 1 7 20 18 9 7 5 18 2 4 12 6 7 1 5 12 4 2 1 Guoliang Xue asu edu HEAPIFY A i LEFT i r RIGHT i if heap size A and A A i then O 1 largest else largest i if r heap size A and A r A largest then largest r if largest i then exchange A i and A largest T 2n 3 HEAPIFY A largest T n worst case running time of HEAPIFY A i on a heap with n elements It is proportional to the height of the tree which is O log n A complete binary tree in particular a heap is balanced 7 Guoliang Xue asu edu Building a Heap How can we build a heap from an arbitrary array A 1 n i e it may not necessarily be a heap bottom up manner using HEAPIFY The elements in the array n 2 1 n are all leaves of the tree each is a 1 element heap to begin with The procedure BUILD HEAP goes through the remaining nodes of the tree and runs HEAPIFY on each node 8 Guoliang Xue asu edu BUILD HEAP A heap size A length A for i length A 2 to 1 do HEAPIFY A i Does the order in which the nodes are processed matter Yes since we need to guarantee that the subtrees rooted at the children of a node i are heaps before HEAPIFY is called at that node BUILD HEAP runs in O n log n time Why Is this a tight bound No The tight upper bound is O n 9 Guoliang Xue asu edu HEAPSORT Any ideas What kind of properties does the heap have HEAPSORT A n BUILD HEAP A for i length A to 2 do n exchange A 1 and A i heap size A O n log n HEAPIFY A 1 O log n per call to HEAPIFY O n log n The maximum element of A is always stored at the root A 1 whenever this property is violated we immediately fix it with HEAPIFY Thus it can be correctly put in place by exchanging A 1 with A heap size A Let n length A A n contains maximum element in A 1 n A n 1 contains second maximum element in A 1 n Guoliang Xue asu edu 10 A n A n 1 A 1 After applying HEAPSORT A 20 15 10 10 2 5 7 9 Exchange A 1 A n 8 15 10 10 9 2 5 2 5 15 20 n 1 n 1 2 4 8 15 8 9 20 10 15 n 1 2 3 7 9 6 10 7 10 5 2 Heapify 7 7 8 9 15 n 1 7 8 8 Exchange A 1 A n 1 10 20 n 10 5 7 8 20 n 1 2 3 4 5 6 2 5 7 8 9 10 10 15 20 11 5 20 n 10 2 10 9 10 9 n 2 5 5 7 8 2 Exchange 10 7 10 20 n 8 9 15 Heapify 9 n 9 A Guoliang Xue asu edu Comparing the Sorting Algorithms worst case running time sort in place INSERTION SORT O n2 yes MERGE SORT O n log n no QUICKSORT HEAPSORT O n2 yes O n log n yes In fact QUICKSORT performs much better on the average than its O n2 worst case running time suggests For QUICKSORT worst case input is not the average case input In practice QUICKSORT outperforms all other sorting algorithms Guoliang Xue asu edu hidden constants are small 12 We can actually place a better upper bound on the running time of BUILD HEAP by noting that we call HEAPIFY on at most n 2h 1 nodes of height h Thus the total running time of BUILD HEAP is log n log n n 2h 1 h O n h 2h O n h 0 h 0 For more details on how we obtained the summation above and how this summation solved to O n please see the textbook p 1148 For the purpose of this course I just want to remember that BUILD HEAP runs in n time 13 Guoliang Xue asu edu We saw in class that HEAPSORT runs in O n log n time since n BUILD …
View Full Document
Unlocking...