《算法课件全121301ADA13变治法堆排序》由会员分享，可在线阅读，更多相关《算法课件全121301ADA13变治法堆排序（41页珍藏版）》请在金锄头文库上搜索。
1、2019/6/21,2,2012-2013-01 Design and Analysis of Algorithm SCUN,2,Review of last class,Transformation and Conquer technique and Its three major variations Gaussian Elimination method Hornors rule,Transform and Conquer (II),Chapter 6,Its Application to Sort Problem Heap Sort,2019/6/21,4,2012-2013-01 D
2、esign and Analysis of Algorithm SCUN,4,Goals of the Lecture,At the end of this lecture, you should Be familiar with the concept and properties of heap Master the heap sort algorithm and its analysis,2019/6/21,5,2012-2013-01 Design and Analysis of Algorithm SCUN,5,The concept of Heap,From the above d
3、efinition, we can regard a heap as a binary tree which satisfied the following two conditions: Trees shape requirement: the binary tree is essentially complete, i.e., all its levels are full except possibly the last level, where only some rightmost keys may be missing Parental dominance requirement:
4、 The element at each node is elements at its children,Definition Given a list r1,r2, , rn, we call this list as a heap if and only if the elements of the list satisfies: ri r2i and ri r2i+1 , 1 i n/2 or satisfies: ri r2i and ri r2i+1 , 1 i n/2,2019/6/21,6,2012-2013-01 Design and Analysis of Algorith
5、m SCUN,6,Illustration of the heaps definition,a heap?,a heap?,a heap?,Note: Heaps elements are ordered top down (along any path down from its root), but they are not ordered left to right,2019/6/21,7,2012-2013-01 Design and Analysis of Algorithm SCUN,7,Some Important Properties of a Heap,There exist
6、s a unique binary tree with n nodes that is essentially complete, with h = log2 n The root contains the largest element The subtree rooted at any node of a heap is also a heap All the leaf nodes are on level h or level h-1 There are 2i nodes on level i, where 0 i h-1 The branch nodes on level h-1 ar
7、e focus on the leftmost Each nodes element is greater than its descendents,2019/6/21,8,2012-2013-01 Design and Analysis of Algorithm SCUN,8,To represent a complete binary tree as an array: The root node is A1 Node i is Ai The parent of node i is Ai/2 (note: integer divide) The left child of node i i
8、s A2i The right child of node i is A2i + 1,Heaps Array Representation,2019/6/21,9,2012-2013-01 Design and Analysis of Algorithm SCUN,9,Stage 1(Heap Construction): transform a given list of n elements into a heap Stage 2(Maximum deletions): Repeat operation of root element removal n-1 times to the re
9、maining heap: Exchange element in the root and in the last (rightmost) leaf Decrease heap size by 1 If necessary, swap new root with larger child until the heap condition holds,Heapsort (basic idea),2019/6/21,10,2012-2013-01 Design and Analysis of Algorithm SCUN,10,Construct the heap for i = 1 to n-
10、1 do copy the root to the list fix the heap end for,Heapsort (algorithm description),The general algorithm can be written as:,2019/6/21,11,2012-2013-01 Design and Analysis of Algorithm SCUN,11,There are two methods for constructing a heap: The first method is the so called bottom-up heap constructio
11、n method The second method is the so called top-down heap construction method,Construction of a heap,2019/6/21,12,2012-2013-01 Design and Analysis of Algorithm SCUN,12,Bottom-up heap construction,Step 0: Initialize the almost complete binary tree with elements in the given order Step 1: Starting wit
12、h the last (rightmost) parental node, check whether the parental dominance holds , if not Step 1.1: exchange the nodes element with the larger element of its children node Step 1.2: check whether the parental dominance holds for the element in its new position, if not repeat step 1.1 Step 2: Repeat
13、Step 1 for the preceding parental node,2019/6/21,13,2012-2013-01 Design and Analysis of Algorithm SCUN,13,Heap Construction Example,2019/6/21,14,2012-2013-01 Design and Analysis of Algorithm SCUN,14,Heap Construction Example,16,4,10,14,7,9,3,2,8,1,16,4,10,14,9,3,2,8,1,A =,7,2019/6/21,15,2012-2013-01
14、 Design and Analysis of Algorithm SCUN,15,Heap Construction Example,16,4,10,14,7,9,3,2,8,1,16,4,10,7,9,3,2,8,1,A =,14,2019/6/21,16,2012-2013-01 Design and Analysis of Algorithm SCUN,16,Heap Construction Example,16,4,10,14,7,9,3,2,8,1,16,4,14,7,9,3,2,8,1,A =,10,2019/6/21,17,2012-2013-01 Design and An
15、alysis of Algorithm SCUN,17,Heap Construction Example,16,4,10,14,7,9,3,2,8,1,16,10,14,7,9,3,2,8,1,A =,4,2019/6/21,18,2012-2013-01 Design and Analysis of Algorithm SCUN,18,Heap Construction Example,16,4,10,14,7,9,3,2,8,1,16,10,7,9,3,2,8,1,A =,4,14,2019/6/21,19,2012-2013-01 Design and Analysis of Algo
16、rithm SCUN,19,Heap Construction Example,16,14,10,4,7,9,3,2,8,1,16,14,10,7,9,3,2,8,1,A =,4,2019/6/21,20,2012-2013-01 Design and Analysis of Algorithm SCUN,20,Heap Construction Example,16,14,10,4,7,9,3,2,8,1,16,14,10,7,9,3,2,1,A =,4,8,2019/6/21,21,2012-2013-01 Design and Analysis of Algorithm SCUN,21,Heap Construction Example,16,14,10,8,7,9,3,2,4,1,16,14,10,8,7,9,3,
