[ 資料結構 小學堂 ] 排序 : 堆積排序法

前言 :
堆積排序法 可以算是 選擇排序法 的改進版, 它可以減少在選擇排序中的比較次數, 進而減少排序時間. 堆積排序法使用到 二元樹 的技巧, 它是利用堆積樹來完成排序. 堆積是一種特殊的二元樹, 可以分為最大堆積樹及最小堆積樹兩種. 而最大堆積數滿足以下3 個條件 :

1. 它是一個完整二元樹.
2. 所有節點的值都大於或等於它右子點的值.
3. 樹根是堆積樹中最大的.

而最小堆積數則具備以下3個條件 :

1. 它是一個完整二元樹.
2. 所有節點的值都小於或等於它右子點的值.
3. 樹根是堆積樹中最小的.

在開始討論堆積排序法前, 先介紹如何將二元樹轉換成堆積數 (Heap Tree). 將以下面實例進行說明 :

Step1 : A[0] = 32 為樹根, A[1] = 17 < A[0] = 32, 不用交換.
Step2 : A[2] = 16 < A[0], 不用交換
Step3 : A[3] = 24 > A[1] = 17 故交換. A[3] = 24 < A[0] = 32, 不用交換

Step4 : A[4] = 35 > A[1] = 24 故交換, A[1] = 35 > A[0] 故交換

Step5 : A[5] = 87 > A[2] = 16 故交換, A[2] = 87 > A[0] = 35 故交換

Step6 : A[6] = 65 > A[2] = 35 故交換, A[2] = 65 < A[0] = 87 故不必交換. 最後 A[7] 與 A[8] 都不必交換, 所以下面為最後的堆積數.

藉由上面示範由二元樹轉換成堆積數, 可以知道堆積樹並非唯一. 至於堆積排序法的演算法就是從樹根取出最大值後, 再從原來的堆積數重新建立堆積數, 然後再依序從樹根取出值來得到排序的結果, 直到原來的堆積數元素為零為止.

堆積演算法分析 :

1. 在所有情況下, 時間複雜度均為 O(nlogn).
2. 堆積排序法不是穩定排序法.
3. 只要一額外空間, 空間複雜度為 O(1).

範例代碼 :

view plaincopy to clipboardprint?

1. #include   
2. #include   
3.   
4. using namespace std;  
5.   
6. struct BenchMark {  
7.     int swapTime;  // Swap Time  
8.     int verifyTime;  // Verify Time  
9.     double cTime;  // Consumed Time  
10. };  
11. void _swapValue(int *a, int *b) {  
12.     int tmp = *a;  
13.     *a = *b;  
14.     *b = tmp;  
15. }  
16.   
17. int _gp(int v) {  
18.     if(v>0) {  
19.         int tmp = v/2;  
20.         if(v%2==0)  
21.             return tmp-1;  
22.         else  
23.             return tmp;  
24.     }     
25.     return 0;  
26. }  
27.   
28. BenchMark _ad_heap(int data[], int i, int size) {  
29.     BenchMark bm;  
30.     int vt=0, st=0;  
31.     for(int j=i; j>0; j--) {  
32.         int tmp = j;  
33.         int k = _gp(j);  
34.         while(k>=0) {  
35.             vt++;  
36.             if(data[tmp] > data[k]) {  
37.                 st++;  
38.                 _swapValue(&data[tmp], &data[k]);  
39.                 tmp = k;  
40.             } else {  
41.                 break;  
42.             }  
43.             if(k==0)  
44.                 break;  
45.             k = _gp(k);  
46.         }  
47.     }  
48.     bm.swapTime = st;  
49.     bm.verifyTime = vt;  
50.     return bm;  
51. }  
52.   
53. BenchMark heapSort(int data[], int size) {  
54.     BenchMark bm;  
55.     BenchMark tmpBM;  
56.     bm.swapTime = 0;  
57.     bm.verifyTime = 0;  
58.     /*建立堆積樹*/  
59.     tmpBM = _ad_heap(data, size, size);  
60.     bm.swapTime+= tmpBM.swapTime;  
61.     bm.verifyTime+=tmpBM.verifyTime;  
62.     printf("堆積樹內容: \n");  
63.     for(int i=0; i
64.         printf("%2d ", data[i]);  
65.     }  
66.     printf("\n");  
67.     for(int i=(size-1); i>=0; i--) {  
68.         _swapValue(&data[i], &data[0]);  
69.         tmpBM = _ad_heap(data, i-1,size);  
70.         bm.swapTime+= tmpBM.swapTime;  
71.         bm.verifyTime+=tmpBM.verifyTime;  
72.     }  
73.     return bm;  
74. }  
75.   
76. void _showData(int data[], int size) {  
77.     for(int i=0; i
78.         printf("%2d ", data[i]);  
79.     }  
80.     printf("\n");  
81. }  
82.   
83. #define HEAP_DATA_SIZE 9  
84. void main(bool b) {  
85.     int data[HEAP_DATA_SIZE] = {32, 17, 16, 24, 35, 87, 65, 4, 12};  
86.     printf("原始資料為: ");  
87.     _showData(data, HEAP_DATA_SIZE);  
88.     BenchMark bm = heapSort(data, HEAP_DATA_SIZE);  
89.     cout << "堆積排序: " << endl;  
90.     _showData(data, HEAP_DATA_SIZE);  
91.     printf("Swap time: %d\n", bm.swapTime);  
92.     printf("Verify time: %d\n", bm.verifyTime);  
93. }  

執行結果 :

原始資料為: 32 17 16 24 35 87 65 4 12
堆積樹內容:
87 35 65 24 17 32 16 4 12
堆積排序:
4 12 16 17 24 32 35 65 87
Swap time: 21
Verify time: 44

Ruby Sample Code

- alg/sort/SortMod.rb 

view plaincopy to clipboardprint?

1. module SortMod    
2.   @@des_cmp = lambda{ |a,b| return a <=> b}  
3.   @@asc_cmp = lambda{ |a,b| return b <=> a}  
4.     
5.   # Open API: Sorting given array.  
6.   def sort(ary, desc=true)  
7.     nary = []  
8.     ary.each{ |item|; nary << item; }  
9.     csort(nary, desc ? @@des_cmp : @@asc_cmp)  
10.     nary  
11.   end  
12.     
13.   # Customized sorting algorithm.  
14.   def csort(ary, cmp)  
15.     raise RuntimeError, "Muse implement method!"  
16.   end  
17.     
18.   # Swap ary[i] with ary[j]  
19.   def swap(ary, i, j)  
20.     ary[i], ary[j] = ary[j], ary[i]  
21.   end  
22.     
23.   # Open API: In place sorting on given array  
24.   def sort?(ary, cmp, desc=true)      
25.     csort(ary, cmp, desc ? @@des_cmp : @@asc_cmp)  
26.     cmp  
27.   end  
28.     
29.   public :sort, :sort?  
30.   protected :csort, :swap    
31. end  

- alg/sort/HeapSort.rb 

view plaincopy to clipboardprint?

1. require "alg/sort/SortMod"  
2.   
3. class HeapSort  
4.   # http://localhost/jforum/posts/list/963.page  
5.   include SortMod  
6.     
7.   # Get Parent  
8.   #             0  
9.   #           1   2  
10.   #          3 4 5 6  
11.   #  p = (c-1)/2  
12.   #  c=1 -> (1-1)/2 = 0  
13.   #  c=2 -> (2-1)/2 = 0  
14.   #  c=3 -> (3-1)/2 = 1  
15.   #  c=4 -> (4-1)/2 = 1  
16.   #  c=5 -> (5-1)/2 = 2  
17.   #  c=6 -> (6-1)/2 = 2    
18.   @@GP=lambda{|c| (c-1)/2}  
19.     
20.   # Get Child  
21.   #             0  
22.   #           1   2  
23.   #          3 4 5 6  
24.   # c = (p*2+1, p*2+2)  
25.   # p=0 -> 0*2+1=1, 0*2+2=2  
26.   # p=1 -> 1*2+1=3, 1*2+2=4  
27.   # p=2 -> 2*2+1=5, 2*2+2=6  
28.   @@GC=lambda{|p| [p*2+1,p*2+2]}       
29.       
30.   # Build heap-tree  
31.   def _ad_heap(ary, cmp, size)  
32.     (size-1).downto(1) do |i|  
33.       p=@@GP.call(i)  
34.       while p>=0  
35.         if cmp.call(ary[i], ary[p])==1  
36.           swap(ary, i, p)  
37.           i=p  
38.           p=@@GP.call(p)  
39.         else  
40.           break  
41.         end  
42.       end  
43.     end  
44.   end  
45.     
46.   def csort(ary, cmp)  
47.     if ary.size > 1  
48.       ary.size.downto(2) do |i|  
49.         _ad_heap(ary, cmp, i)  
50.         #printf("HeapTree(%d)=%s\n", i, ary)  
51.         swap(ary, 0, i-1)  
52.       end        
53.     end  
54.     ary   
55.   end  
56. end  

- Demo Code 

view plaincopy to clipboardprint?

1. require "alg/sort/HeapSort"  
2.   
3. printf("Heap Sorting Demo:\n")  
4. heapSort = HeapSort.new  
5. printf("Original ary: %s\n", a)  
6. printf("After sort(desc): %s\n", heapSort.sort(a, false))  
7. printf("After sort(asc) : %s\n", heapSort.sort(a, true))  
8. printf("Original ary: %s\n\n", a)  

Execution result: 

Heap Sorting Demo:
Original ary: [2, 5, 9, 7, 6, 4, 8, 1, 3]
After sort(desc): [9, 8, 7, 6, 5, 4, 3, 2, 1]
After sort(asc) : [1, 2, 3, 4, 5, 6, 7, 8, 9]
Original ary: [2, 5, 9, 7, 6, 4, 8, 1, 3]

補充說明 :
* Wiki : Heapsort

Heapsort is a comparison-based sorting algorithm, and is part of the selection sort family. Although somewhat slower in practice on most machines than a good implementation of quicksort, it has the advantage of a more favorable worst-case Θ(n log n) runtime. Heapsort is an in-place algorithm, but is not a stable sort.