Question? Leave a message!

Heap sort

Heap sort
Dr.SethPatton Profile Pic
Dr.SethPatton,United Kingdom,Teacher
Published Date:22-07-2017
Website URL
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 © 2006-2013 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 min-heap 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 double-precision floating-point number it is difficult to calculate ln(n) Often a function lgamma, ln_gamma 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 In-place Implementation Problem: – This solution requires additional memory, that is, a min-heap 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 In-place Implementation Instead of implementing a min-heap, consider a max-heap: – A heap where the maximum element is at the top of the heap and the next to be poppedHeap sort 10 8.4.2 In-place Heapification Now, consider this unsorted array: This array represents the following complete tree: This is neither a min-heap, max-heap, or binary search treeHeap sort 11 8.4.2 In-place 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 In-place Heapification Can we convert this complete tree into a max heap? Restriction: – The operation must be done in-placeHeap sort 13 In-place Heapification Two strategies: – Assume 46 is a max-heap 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 In-place Heapification Let’s work bottom-up: each leaf node is a max heap on its ownHeap sort 15 8.4.3 In-place Heapification Starting at the back, we note that all leaf nodes are trivial heaps Also, the subtree with 87 as the root is a max-heapHeap sort 16 8.4.3 In-place Heapification The subtree with 23 is not a max-heap, but swapping it with 55 creates a max-heap This process is termed percolating downHeap sort 17 8.4.3 In-place Heapification The subtree with 3 as the root is not max-heap, but we can swap 3 and the maximum of its children: 86Heap sort 18 8.4.3 In-place Heapification Starting with the next higher level, the subtree with root 48 can be turned into a max-heap by swapping 48 and 99Heap sort 19 8.4.3 In-place Heapification Similarly, swapping 61 and 95 creates a max-heap of the next subtreeHeap sort 20 8.4.3 In-place Heapification As does swapping 35 and 92