Question? Leave a message!

Heap sort

Heap sort
ECE 250 Algorithms and Data Structures Heap sort Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada © 20062013 by Douglas Wilhelm Harder. Some rights reserved.Heap sort 2 Outline This topic covers the simplest Q(n ln(n)) sorting algorithm: heap sort We will: – define the strategy – analyze the run time – convert an unsorted list into a heap – cover some examples Bonus: may be performed in placeHeap sort 3 8.4.1 Heap Sort Recall that inserting n objects into a minheap and then taking n objects will result in them coming out in order Strategy: given an unsorted list with n objects, place them into a heap, and take them outHeap sort 4 8.4.1 Run time Analysis of Heap Sort Taking an object out of a heap with n items requires O(ln(n)) time Therefore, taking n objects out requires n n   ln(k) ln k lnn   k1 k1  Recall that ln(a) + ln(b) = ln(ab) Question: What is the asymptotic growth of ln(n)Heap sort 5 8.4.1 Run time Analysis of Heap Sort Using Maple: asympt( ln( n ), n );  1 1 1 1              (ln(n) 1) n ln( 2 ) ln(n) O   2 12n 3 5 360nn The leading term is (ln(n) – 1) n Therefore, the run time is O(n ln(n))Heap sort 6 8.4.1 ln(n) and n ln(n) A plot of ln(n) and n ln(n) also suggests that they are asymptotically related:Heap sort 7 8.4.1 Aside: Calculating ln(n) Due to the incredible growth of n – 200 cannot be represented by a doubleprecision floatingpoint number it is difficult to calculate ln(n) Often a function lgamma, lngamma or lnGAMMA is defined to calculate ln(n) without the intermediate calculation of n The actual definition is ln( n ) == lgamma( n + 1 )Heap sort 8 8.4.2 Inplace Implementation Problem: – This solution requires additional memory, that is, a minheap of size n This requires Q(n) memory and is therefore not in place Is it possible to perform a heap sort in place, that is, require at most Q(1) memory (a few extra variables)Heap sort 9 8.4.2 Inplace Implementation Instead of implementing a minheap, consider a maxheap: – A heap where the maximum element is at the top of the heap and the next to be poppedHeap sort 10 8.4.2 Inplace Heapification Now, consider this unsorted array: This array represents the following complete tree: This is neither a minheap, maxheap, or binary search treeHeap sort 11 8.4.2 Inplace Heapification Now, consider this unsorted array: Additionally, because arrays start at 0 (we started at entry 1 for binary heaps) , we need different formulas for the children and parent The formulas are now: Children 2k + 1 2k + 2 Parent (k + 1)/2 1Heap sort 12 8.4.2 Inplace Heapification Can we convert this complete tree into a max heap Restriction: – The operation must be done inplaceHeap sort 13 Inplace Heapification Two strategies: – Assume 46 is a maxheap and keep inserting the next element into the existing heap (similar to the strategy for insertion sort) – Start from the back: note that all leaf nodes are already max heaps, and then make corrections so that previous nodes also form max heapsHeap sort 14 8.4.3 Inplace Heapification Let’s work bottomup: each leaf node is a max heap on its ownHeap sort 15 8.4.3 Inplace Heapification Starting at the back, we note that all leaf nodes are trivial heaps Also, the subtree with 87 as the root is a maxheapHeap sort 16 8.4.3 Inplace Heapification The subtree with 23 is not a maxheap, but swapping it with 55 creates a maxheap This process is termed percolating downHeap sort 17 8.4.3 Inplace Heapification The subtree with 3 as the root is not maxheap, but we can swap 3 and the maximum of its children: 86Heap sort 18 8.4.3 Inplace Heapification Starting with the next higher level, the subtree with root 48 can be turned into a maxheap by swapping 48 and 99Heap sort 19 8.4.3 Inplace Heapification Similarly, swapping 61 and 95 creates a maxheap of the next subtreeHeap sort 20 8.4.3 Inplace Heapification As does swapping 35 and 92Heap sort 21 8.4.3 Inplace Heapification The subtree with root 24 may be converted into a maxheap by first swapping 24 and 86 and then swapping 24 and 28Heap sort 22 8.4.3 Inplace Heapification The rightmost subtree of the next higher level may be turned into a maxheap by swapping 77 and 99Heap sort 23 8.4.3 Inplace Heapification However, to turn the next subtree into a maxheap requires that 13 be percolated down to a leaf nodeHeap sort 24 8.4.3 Inplace Heapification The root need only be percolated down by two levelsHeap sort 25 8.4.3 Inplace Heapification The final product is a maxheapHeap sort 26 Runtime Analysis of Heapify Considering a perfect tree of height h: – The maximum number of swaps which a secondlowest level would experience is 1, the next higher level, 2, and so onHeap sort 27 Runtime Analysis of Heapify k At depth k, there are 2 nodes and in the worst case, all of these nodes would have to percolated down h– k levels k – In the worst case, this would requiring a total of 2 (h– k) swaps Writing this sum mathematically, we get: h k h1 2hk21 (h1)  k0Heap sort 28 Runtime Analysis of Heapify h + 1 Recall that for a perfect tree, n = 2– 1 and h + 1 = lg(n + 1), therefore h k 2 hkn lg n1   k0 Each swap requires two comparisons (which child is greatest), so there is a maximum of 2n (or Q(n)) comparisonsHeap sort 29 Runtime Analysis of Heapify Note that if we go the other way (treat the first entry as a max heap and then continually insert new elements into that heap, the run time is at worst h kh1 2kh 21 2   k0 h1  21hh11 2   n lg n1 2 lg n1 4Q nln n  – It is significantly better to start at the backHeap sort 30 8.4.4 Example Heap Sort Let us look at this example: we must convert the unordered array with n = 10 elements into a maxheap None of the leaf nodes need to be percolated down, and the first nonleaf node is in position n/2 Thus we start with position 10/2 = 5Heap sort 31 8.4.4 Example Heap Sort We compare 3 with its child and swap themHeap sort 32 8.4.4 Example Heap Sort We compare 17 with its two children and swap it with the maximum child (70)Heap sort 33 8.4.4 Example Heap Sort We compare 28 with its two children, 63 and 34, and swap it with the largest childHeap sort 34 8.4.4 Example Heap Sort We compare 52 with its children, swap it with the largest – Recursing, no further swaps are neededHeap sort 35 8.4.4 Example Heap Sort Finally, we swap the root with its largest child, and recurse, swapping 46 again with 81, and then again with 70Heap sort 36 8.4.4 Heap Sort Example We have now converted the unsorted array into a maxheap:Heap sort 37 8.4.4 Heap Sort Example Suppose we pop the maximum element of this heap This leaves a gap at the back of the array:Heap sort 38 8.4.4 Heap Sort Example This is the last entry in the array, so why not fill it with the largest element Repeat this process: pop the maximum element, and then insert it at the end of the array:Heap sort 39 8.4.4 Heap Sort Example Repeat this process – Pop and append 70 – Pop and append 63Heap sort 40 8.4.4 Heap Sort Example We have the 4 largest elements in order – Pop and append 52 – Pop and append 46Heap sort 41 8.4.4 Heap Sort Example Continuing... – Pop and append 34 – Pop and append 28Heap sort 42 8.4.4 Heap Sort Example nd Finally, we can pop 17, insert it into the 2 location, and the resulting array is sortedHeap sort 43 8.4.5 Black Board Example Sort the following 12 entries using heap sort 34, 15, 65, 59, 79, 42, 40, 80, 50, 61, 23, 46Heap sort 44 8.4.6 Heap Sort Heapification runs in Q(n) Popping n items from a heap of size n, as we saw, runs in Q(n ln(n)) time – We are only making one additional copy into the blank left at the end of the array Therefore, the total algorithm will run in Q(n ln(n)) timeHeap sort 45 8.4.6 Heap Sort There are no worstcase scenarios for heap sort – Dequeuing from the heap will always require the same number of operations regardless of the distribution of values in the heap There is one best case: if all the entries are identical, then the run time is Q(n) The original order may speed up the heapification, however, this would only speed up an Q(n) portion of the algorithmHeap sort 46 8.4.6 Runtime Summary The following table summarizes the runtimes of heap sort Run Time Case Comments WorstQ(n ln(n)) No worst case AverageQ(n ln(n)) BestQ(n) All or most entries are the sameHeap sort 47 8.4.6 Summary We have seen our first inplace Q(n ln(n)) sorting algorithm: – Convert the unsorted list into a maxheap as complete array – Pop the top n times and place that object into the vacancy at the end – It requires Q(1) additional memory—it is truly inplace It is a nice algorithm; however, we will see two other faster n ln(n) algorithms; however: – Merge sort requires Q(n) additional memory – Quick sort requires Q(ln(n)) additional memoryHeap sort 48 References Wikipedia, nd 1 Donald E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching, 2 Ed., Addison Wesley, 1998, §5.2.3, p.1448. 2 Cormen, Leiserson, and Rivest, Introduction to Algorithms, McGraw Hill, 1990, Ch. 7, p.1409. rd 3 Weiss, Data Structures and Algorithm Analysis in C++, 3 Ed., Addison Wesley, §7.5, p.2704. These slides are provided for the ECE 250 Algorithms and Data Structures course. The material in it reflects Douglas W. Harder’s best judgment in light of the information available to him at the time of preparation. Any reliance on these course slides by any party for any other purpose are the responsibility of such parties. Douglas W. Harder accepts no responsibility for damages, if any, suffered by any party as a result of decisions made or actions based on these course slides for any other purpose than that for which it was intended.
Website URL
Document Information
User Name:
User Type:
United Kingdom
Uploaded Date: