算法课件全121301ADA13变治法堆排序.pptVIP

2007-2008-01《Design and Analysis of Algorithms》SCUEC * Heap Fix algorithm FixHeap(A[1…n], index, value, size) //Input: An array A[1…n] of orderable items, the location index and value value to fix, the size size //Output: A heap A[1…n] valueIndex ? index while 2* valueIndex ≤ size do childIndex ? 2* valueIndex if (childIndex size) and (A[childIndex+1]A[childIndex]) childIndex ? childIndex + 1 if value ≥A[childIndex] break else A[valueIndex] ? A[childIndex]; valueIndex ? childIndex A[valueIndex] ? value * Heap Construction Heap Sort Algorithm HeapBottomUp(A[1…n]) //Input: An array A[1…n] of orderable items //Output: A heap A[1…n] for i ? ?n/2? down to 1 do FixHeap(A, i, A[i], n) HeapSort(A[1…n]) //Input: An array A[1…n] of orderable items //Output: The A[1…n] sorted in ascending order HeapBottomUp(A) for i ? n down to 2 do max ? A[1] FixHeap(A, 1, A[i], i-1) A[i] ? max * Stage 2 (root/max removal) 9 6 8 2 5 7 7 6 8 2 5 | 9 8 6 7 2 5 | 9 5 6 7 2 | 8 9 7 6 5 2 | 8 9 2 6 5 | 7 8 9 6 2 5 | 7 8 9 5 2 | 6 7 8 9 5 2 | 6 7 8 9 2 | 5 6 7 8 9 Example of Sorting by Heapsort Sort the list 2, 9, 7, 6, 5, 8 by heapsort Stage 1 (heap construction) 2 9 7 6 5 8 2 9 8 6 5 7 2 9 8 6 5 7 9 2 8 6 5 7 9 6 8 2 5 7 * Worst-case Analysis (heap construction process) So we get: Suppose there n elements in the list which need to sort, then the binary tree corresponding to the list would have h= ?logn? levels . The elements of level i would sift down h-i levels at most, each sift down need 2 comparisons. There are 2i nodes on level i We only need to do the sift down operation of the elements from level 0 to level h-1 * Worst-case Analysis (maximum deletion process) So the worst case fo