Question? Leave a message!




Heap sort

Heap sort
Dr.SethPatton Profile Pic
Dr.SethPatton,United Kingdom,Teacher
Published Date:22-07-2017
Website URL
Comment
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 ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 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