CSE310 Lecture 09: Heaps and HeapsortTopics of this lectureSlide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide [email protected] Lecture 09:CSE310 Lecture 09:Heaps and HeapsortHeaps and HeapsortGuoliang (Larry) XueDepartment of CSEArizona State Universityhttp://www.fulton.asu.edu/[email protected] of this lectureTopics 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[email protected]= Heaps =• The (binary) heap data structure is an array object that can be viewed as a complete binary tree.Ex:20187512108 94 2 1 71 2 3 4 5 6 7 8 9 10 11 1220 18 10 7 12 8 9 5 4 2 1 7heap.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 [email protected] 94 2 1 71 2 3 4 5 6 7 8 9 10 11 1220 18 10 7 12 8 9 5 4 2 1 7512376121110984PARENT(i) /* parent of i in the treereturn i/2LEFT(i) /* left child of i in the treereturn 2iRIGHT(i) /* right child of i in the treereturn (2i+1)• heap property: for every node i other than root, A[PARENT(i)] > A[i][email protected]• 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 [email protected]• 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 beused as a priority queue. ( O(log n) )= Maintaining the Heap Property =• When heap property is violated at A[i] – i.e., subtrees rooted atLEFT(i) and RIGHT(i) are heaps, but A[i] is smaller than itschildren – then let value of A[i] “float down” the heap.2027518108 94 12 1 7i20187524 12 1201875124 2 [email protected] (A, i) = LEFT(i)r = RIGHT(i)if  < heap-size[A] and A[] > A[i] thenO(1) largest =  elselargest = iif r < heap-size[A] and A[r] > A[largest] thenlargest = rif largest  i thenexchange A[i] and A[largest] T(2n/3) HEAPIFY(A, largest)T(n) = worst-case running time of HEAPIFY(A, i) on a heap withn elements. It is proportional to the height of the tree, which is O(log n).• A complete binary tree (in particular, a heap) is [email protected] 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.= Building a Heap [email protected](A)heap-size[A] = length[A]for i = length[A]/2 to 1 doHEAPIFY(A, i)• Does the order in which the nodes are processed matter?Yes, since we need to guarantee that the subtrees rooted atthe children of a node i are heaps before HEAPIFY is calledat 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)[email protected]= 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]. . .  After applying HEAPSORT(A), A[n] > A[n-1] > … > A[1][email protected] 899151025107 8201510925107 8202109155107 8201092155107 820892155107 1020ExchangeA[1] & A[n]HeapifyExchangeA[1] & A[n-1]HeapifyExchange. . .20158 9 10 105 7241235 6 78 91 2 3 4 5 6 7 8 92 5 7 8 9 10 10 15 20Ann-2n-1n-1 nn-1 nnn(n = 9)[email protected]= Comparing the Sorting Algorithms =worst - caserunning time sort in place?INSERTION-SORT: O(n2) yesMERGE-SORT: O(n log n) noQUICKSORT: O(n2) yesHEAPSORT: 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 ( hidden constants are small )[email protected]• 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.)[email protected]• We saw in class that HEAPSORT runs in O(n log n) time, since(n) - BUILD-HEAP takes O(n) time, and(n) - we make n calls to HEAPIFY (each call to HEAPIFY on an array with n elements takes O(log n) time. (O(log n) per call to HEAPIFY)O(n*log n) O(n*log n) From the sorting lower bound for comparison-based algorithms (HEAPSORT being one such algorithm), we know that HEAPSORT has (n log n) worst-case running time. HEAPSORT has (n log n) worst-case running [email protected]The Heap Data Structure.Delete-MaxIncrease-keyInsertionHeapsort.Build HeapSequential insertion takes O(n log n) time.Buildheap takes O(n) [email protected]The materials covered in this lecture can be found in Section 6.1-6.4.Work on exercises 6.1-1---6.1-7; 6.2-1--6.2-6; 6.3-1--6.3-3;