堆排序

renhl252 2014-09-29

展開全文

【1】完全二叉樹

在學習堆排序之前，我們先要了解一下完全二叉樹。

若設二叉樹的深度為h，除第h層外，其它各層 (1...h-1) 的結點數(shù)都達到最大個數(shù)，第h層所有的結點都連續(xù)集中在最左邊，這就是完全二叉樹。

完全二叉樹特點：

（1）滿二叉樹是完全二叉樹，完全二叉樹不一定是滿二叉樹。

（2）在滿二叉樹的最下一層上，從最右邊開始連續(xù)刪去若干結點后得到的二叉樹仍然是一棵完全二叉樹。

（3）在完全二叉樹中，若某個結點沒有左孩子，則它一定沒有右孩子，即該結點必是葉結點。

（4）如下圖所示，結點C沒有左孩子而有右孩子F，故它不是一棵完全二叉樹。

（5）如下圖所示，兩棵完全二叉樹（右邊b為滿二叉樹）。

（6）下圖是一棵天然的完全二叉樹

【2】堆（Heap）

在程序設計領域，堆(Heap)的概念主要有以下兩種：

（1）一種數(shù)據(jù)結構，邏輯上是一顆完全二叉樹，存儲上是一個數(shù)組對象（二叉堆）。也正是本文談及的堆。

（2）存儲區(qū)，是軟件系統(tǒng)可以編程的內(nèi)存區(qū)域（即就是動態(tài)申請的區(qū)域）。

數(shù)據(jù)結構中的堆實質(zhì)上是滿足一定性質(zhì)的完全二叉樹：二叉樹中任一非葉子結點關鍵字的值均小于（大于）它的孩子結點的關鍵字。

在小根堆中，第一個元素（完全二叉樹的根結點）的關鍵字最?。?/span>

大根堆中，第一個元素（完全二叉樹的根結點）的關鍵字最大，

顯然，堆中任一子樹仍是一個堆。

假設，節(jié)點I是數(shù)組A中下標為i的節(jié)點：

那么，節(jié)點I的父節(jié)點下標為：（i-1）/2

節(jié)點I的左子節(jié)點下標為：2 * i + 1

節(jié)點I的右子節(jié)點下標為：2 * i + 2

詳細圖解如下存儲與邏輯表示

【3】堆存儲與邏輯結構表示

如下圖所示：

注意：示例中的邏輯結構堆不是最大堆也不是最小堆，僅僅只是為了便于理解堆的邏輯結構。

【4】堆排序定義

n個關鍵字序列Kl，K2，…，Kn稱為堆，當且僅當該序列滿足如下性質(zhì)（簡稱為堆性質(zhì)）：

（1) ki ≤ K2i 且 ki ≤ K2i+1 或（2） Ki ≥ K2i 且 ki ≥ K2i+1（（i=1,2,…,[n/2]，其中[]表示上取整）

若將此序列所存儲的向量R[1..n]看做是一棵完全二叉樹的存儲結構，則堆實質(zhì)上是滿足如下性質(zhì)的完全二叉樹：

樹中任一非葉結點的關鍵字均不大于（或不小于）其左右孩子（若存在）結點的關鍵字。

【5】堆排序思想

堆排序利用了大根堆(或小根堆)堆頂（根節(jié)點）記錄的關鍵字最大(或最小)這一特征，使得在當前無序區(qū)中選取最大(或最小)關鍵字的記錄變得簡單。

（1）用大根堆排序的基本思想

<1>先將初始文件R[1.....N]建成一個大根堆，此堆為初始的無序區(qū)。

<2>再將關鍵字最大的記錄R[1](即堆頂)和無序區(qū)的最后一個記錄R[n]交換

由此得到新的無序區(qū)R[1..n-1]和有序區(qū)R[n]，且滿足R[1..n-1].keys ≤ R[n].key

<3>由于交換后新的根R[1]可能違反堆性質(zhì)，故應將當前無序區(qū)R[1..n-1]調(diào)整為堆。

然后再次將R[1..n-1]中關鍵字最大的記錄R[1]和該區(qū)間的最后一個記錄R[n-1]交換

由此得到新的無序區(qū)R[1..n-2]和有序區(qū)R[n-1..n]，且仍滿足關系R[1..n-2].keys ≤ R[n-1..n].keys，同樣要將R[1..n-2]調(diào)整為堆。

直到無序區(qū)只有一個元素為止。

（2）大根堆排序算法的基本操作：

<1> 初始化操作：將R[1..n]構造為初始堆；

<2>每一趟排序的基本操作：將當前無序區(qū)的堆頂記錄R[1]和該區(qū)間的最后一個記錄交換，然后將新的無序區(qū)調(diào)整為堆(亦稱重建堆)。

注意：

<1>只需做n-1趟排序，選出較大的n-1個關鍵字即可以使得文件遞增有序。

<2>用小根堆排序與利用大根堆類似，只不過其排序結果是遞減有序的。

堆排序和直接選擇排序相反：在任何時刻，堆排序中無序區(qū)總是在有序區(qū)之前，且有序區(qū)是在原向量的尾部由后往前逐步擴大至整個向量為止。

（3）排序邏輯結構演示如下圖所示：

請結合以上邏輯分析內(nèi)容或以下實現(xiàn)代碼加深對堆排序的理解。

【6】堆排序?qū)崿F(xiàn)

（1）C++實現(xiàn)與測試代碼如下：

  1 #include<iostream>
  2 using namespace std;
  3 
  4 void swap(int &a,int &b)
  5 {
  6     int temp = a;
  7     a = b;
  8     b = temp;
  9 }
 10 
 11 void  PrintArr(int ar[],int n)
 12 {
 13     for(int i = 0; i < n; ++i)
 14         cout<<ar[i]<<" ";
 15     cout<<endl;
 16 }
 17 
 18 void AdjustHeap(int data[], int start, int m)  
 19 {  
 20     int i = 0, j = 0;  
 21     int value = data[start];  
 22     for(i = start, j = 2*i + 1; j <= m; i = j, j = 2*j+1)  
 23     {  
 24         cout<<"i = "<<i<<" j = "<<j<<" value = "<<value<<endl;
 25         if(j < m  && data[j] < data[j+1])  
 26         {
 27             ++j;
 28         }
 29         if(value > data[j])    
 30             break;  
 31         else   
 32             data[i] = data[j];     
 33         PrintArr(data, 6);
 34     }  
 35     data[i] = value; 
 36     PrintArr(data, 6);
 37 }  
 38 
 39 void HeapSort(int data[],int size)
 40 {
 41     int i = 0;
 42     cout<<"調(diào)整為最大堆的過程："<<endl;
 43     for(i = size/2-1; i >= 0; --i)
 44     {
 45         cout<<"i = "<<i<<" size = "<<size<<endl;
 46         AdjustHeap(data, i, size-1);
 47     }
 48     cout<<"調(diào)整為最大堆結果如下："<<endl;
 49     PrintArr(data, size);
 50     cout<<"整個排序過程如下："<<endl;
 51     for(i = size - 1; i >= 1; --i)
 52     {
 53         swap(data[0], data[i]);
 54         PrintArr(data, size);
 55         AdjustHeap(data, 0, i-1);        
 56         PrintArr(data, size);
 57     }
 58 } 
 59 
 60 void  main()
 61 {
 62     int  ar[] = {12, 88, 32, 5, 16, 67};
 63     int len = sizeof(ar)/sizeof(int);
 64     cout<<"原數(shù)據(jù)序列為："<<endl;
 65     PrintArr(ar, len);
 66     HeapSort(ar, len);
 67     cout<<"排序后結果如下："<<endl;
 68     PrintArr(ar, len);
 69 } 
 70 /*
 71 原數(shù)據(jù)序列為：
 72 12 88 32 5 16 67
 73 調(diào)整為最大堆的過程：
 74 i = 2 size = 6
 75 i = 2 j = 5 value = 32
 76 12 88 67 5 16 67
 77 12 88 67 5 16 32
 78 i = 1 size = 6
 79 i = 1 j = 3 value = 88
 80 12 88 67 5 16 32
 81 i = 0 size = 6
 82 i = 0 j = 1 value = 12
 83 88 88 67 5 16 32
 84 i = 1 j = 3 value = 12
 85 88 16 67 5 16 32
 86 88 16 67 5 12 32
 87 調(diào)整為最大堆結果如下：
 88 88 16 67 5 12 32
 89 整個排序過程如下：
 90 32 16 67 5 12 88
 91 i = 0 j = 1 value = 32
 92 67 16 67 5 12 88
 93 67 16 32 5 12 88
 94 67 16 32 5 12 88
 95 12 16 32 5 67 88
 96 i = 0 j = 1 value = 12
 97 32 16 32 5 67 88
 98 32 16 12 5 67 88
 99 32 16 12 5 67 88
100 5 16 12 32 67 88
101 i = 0 j = 1 value = 5
102 16 16 12 32 67 88
103 16 5 12 32 67 88
104 16 5 12 32 67 88
105 12 5 16 32 67 88
106 i = 0 j = 1 value = 12
107 12 5 16 32 67 88
108 12 5 16 32 67 88
109 5 12 16 32 67 88
110 5 12 16 32 67 88
111 5 12 16 32 67 88
112 排序后結果如下：
113 5 12 16 32 67 88
114  */

（2）堆排序代碼示例：

 1 void swap(int &a,int &b)
 2 {
 3     int temp = a;
 4     a = b;
 5     b = temp;
 6 }
 7 
 8 void AdjustHeap(int data[], int start, int m)  
 9 {  
10     int i = 0, j = 0;  
11     int value = data[start];  
12     for(i = start, j = 2*i + 1; j <= m; i = j, j = 2*j+1)  
13     {  
14         if(j < m  && data[j] < data[j+1])  
15         {
16             ++j;
17         }
18         if(value > data[j])    
19             break;  
20         else   
21             data[i] = data[j];     
22     }  
23     data[i] = value; 
24 
25 }  
26 
27 void HeapSort(int data[],int size)
28 {
29     int i = 0;
30     for(i = size/2-1; i >= 0; --i)
31     {
32         AdjustHeap(data, i, size-1);
33     }
34     for(i = size - 1; i >= 1; --i)
35     {
36         swap(data[0], data[i]);
37         AdjustHeap(data, 0, i-1);        
38     }
39 }