HeapsortSlide 2Data Structure Binary HeapHeap Property (Max and Min)Heaps – ExampleHeightHeaps in SortingHeap CharacteristicsMaintaining the heap propertyMaxHeapify – ExampleProcedure MaxHeapifyRunning Time for MaxHeapifyRunning Time for MaxHeapify(A, n)Building a heapBuildMaxHeap – ExampleSlide 16Correctness of BuildMaxHeapRunning Time of BuildMaxHeapSlide 19Slide 20Heapsort(A)Heapsort – ExampleSlide 23Algorithm AnalysisHeap Procedures for SortingPriority QueueBasic OperationsSlide 28Heap-Extract-Max(A)Heap-Insert(A, key)Heap-Increase-Key(A, i, key)ExamplesHeapsortHeapsortMany of the slides are from Prof. Plaisted’s resources at University of North Carolina at Chapel HillHeapsortCombines the better attributes of merge sort and insertion sort.»Like merge sort, but unlike insertion sort, running time is O(n lg n).»Like insertion sort, but unlike merge sort, sorts in place.Introduces an algorithm design technique »Create data structure (heap) to manage information during the execution of an algorithm.The heap has other applications beside sorting.»Priority QueuesData Structure Binary Heap Array viewed as a nearly complete binary tree.»Physically – linear array.»Logically – binary tree, filled on all levels (except lowest.)Map from array elements to tree nodes and vice versa»Root – A[1]»Left[i] – A[2i]»Right[i] – A[2i+1]»Parent[i] – A[i/2]length[A] – number of elements in array A.heap-size[A] – number of elements in heap stored in A.»heap-size[A]  length[A]Heap Property (Max and Min)Max-Heap»For every node excluding the root, value is at most that of its parent: A[parent[i]]  A[i]Largest element is stored at the root.In any subtree, no values are larger than the value stored at subtree root.Min-Heap»For every node excluding the root, value is at least that of its parent: A[parent[i]]  A[i] Smallest element is stored at the root.In any subtree, no values are smaller than the value stored at subtree rootHeaps – Example 26 24 20 18 17 19 13 12 14 11 1 2 3 4 5 6 7 8 9 102624 20181719131214 11Max-heap as anarray.Max-heap as a binarytree.Last row filled from left to right.HeightHeight of a node in a tree: the number of edges on the longest simple downward path from the node to a leaf.Height of a tree: the height of the root.Height of a heap: lg n »Basic operations on a heap run in O(lg n) timeHeaps in SortingUse max-heaps for sorting.The array representation of max-heap is not sorted.Steps in sorting»Convert the given array of size n to a max-heap (BuildMaxHeap)»Swap the first and last elements of the array.•Now, the largest element is in the last position – where it belongs.•That leaves n – 1 elements to be placed in their appropriate locations.•However, the array of first n – 1 elements is no longer a max-heap.•Float the element at the root down one of its subtrees so that the array remains a max-heap (MaxHeapify)•Repeat step 2 until the array is sorted.Heap CharacteristicsHeight = lg nNo. of leaves = n/2No. of nodes of height h  n/2h+1Maintaining the heap propertySuppose two subtrees are max-heaps, but the root violates the max-heap property.Fix the offending node by exchanging the value at the node with the larger of the values at its children. »May lead to the subtree at the child not being a heap.Recursively fix the children until all of them satisfy the max-heap property.MaxHeapify – Example 2614 2024171913121811141424241414181814MaxHeapify(A, 2)Procedure MaxHeapifyMaxHeapify(A, i)1. l  left(i)2. r  right(i)3. if l  heap-size[A] and A[l] > A[i]4. then largest  l5. else largest  i6. if r  heap-size[A] and A[r] > A[largest]7. then largest  r8. if largest i9. then exchange A[i]  A[largest]10. MaxHeapify(A, largest)MaxHeapify(A, i)1. l  left(i)2. r  right(i)3. if l  heap-size[A] and A[l] > A[i]4. then largest  l5. else largest  i6. if r  heap-size[A] and A[r] > A[largest]7. then largest  r8. if largest i9. then exchange A[i]  A[largest]10. MaxHeapify(A, largest)Assumption:Left(i) and Right(i) are max-heaps.Running Time for MaxHeapifyMaxHeapify(A, i)1. l  left(i)2. r  right(i)3. if l  heap-size[A] and A[l] > A[i]4. then largest  l5. else largest  i6. if r  heap-size[A] and A[r] > A[largest]7. then largest  r8. if largest i9. then exchange A[i]  A[largest]10. MaxHeapify(A, largest)MaxHeapify(A, i)1. l  left(i)2. r  right(i)3. if l  heap-size[A] and A[l] > A[i]4. then largest  l5. else largest  i6. if r  heap-size[A] and A[r] > A[largest]7. then largest  r8. if largest i9. then exchange A[i]  A[largest]10. MaxHeapify(A, largest)Time to fix node i and its children = (1)Time to fix the subtree rooted at one of i’s children = T(size of subree at largest)PLUSRunning Time for MaxHeapify(A, n) T(n) = T(largest) + (1) largest  2n/3 (worst case occurs when the last row of tree is exactly half full)T(n)  T(2n/3) + (1)  T(n) = O(lg n) Alternately, MaxHeapify takes O(h) where h is the height of the node where MaxHeapify is appliedBuilding a heapUse MaxHeapify to convert an array A into a max-heap.How?Call MaxHeapify on each element in a bottom-up manner.BuildMaxHeap(A)1. heap-size[A]  length[A]2. for i  length[A]/2 downto 13. do MaxHeapify(A, i)BuildMaxHeap(A)1. heap-size[A]  length[A]2. for i  length[A]/2 downto 13. do MaxHeapify(A, i)BuildMaxHeap – Example 24 21 23 22 36 29 30 34 28 27Input Array:2421 23223629303428 27Initial Heap:(not max-heap)BuildMaxHeap – Example 242123223629303428 27MaxHeapify(10/2 = 5)3636MaxHeapify(4)223422MaxHeapify(3)233023MaxHeapify(2)213621MaxHeapify(1)24362434242824212127Correctness of BuildMaxHeapLoop Invariant: At the start of each iteration of the for loop, each node i+1, i+2, …, n is the root of a max-heap.Initialization: »Before first iteration i = n/2»Nodes n/2+1, n/2 +2, …, n are leaves and hence roots of max-heaps.Maintenance:»By LI, subtrees at children of node i are max heaps.»Hence, MaxHeapify(i) renders node i a max heap root (while