|
【1】完全二叉樹 在學(xué)習(xí)堆排序之前，我們先要了解一下完全二叉樹。 若設(shè)二叉樹的深度為h，除第h層外，其它各層 (1...h-1) 的結(jié)點(diǎn)數(shù)都達(dá)到最大個數(shù)，第h層所有的結(jié)點(diǎn)都連續(xù)集中在最左邊，這就是完全二叉樹。 完全二叉樹特點(diǎn)： （1） 滿二叉樹是完全二叉樹，完全二叉樹不一定是滿二叉樹。 （2） 在滿二叉樹的最下一層上，從最右邊開始連續(xù)刪去若干結(jié)點(diǎn)后得到的二叉樹仍然是一棵完全二叉樹。 （3） 在完全二叉樹中，若某個結(jié)點(diǎn)沒有左孩子，則它一定沒有右孩子，即該結(jié)點(diǎn)必是葉結(jié)點(diǎn)。 （4）如下圖所示，結(jié)點(diǎn)C沒有左孩子而有右孩子F，故它不是一棵完全二叉樹。
（5）如下圖所示，兩棵完全二叉樹（右邊b為滿二叉樹）。
（6）下圖是一棵天然的完全二叉樹
【2】堆（Heap） 在程序設(shè)計(jì)領(lǐng)域，堆(Heap)的概念主要有以下兩種： （1）一種數(shù)據(jù)結(jié)構(gòu)，邏輯上是一顆完全二叉樹，存儲上是一個數(shù)組對象（二叉堆）。也正是本文談及的堆。 （2）存儲區(qū)，是軟件系統(tǒng)可以編程的內(nèi)存區(qū)域（即就是動態(tài)申請的區(qū)域）。 數(shù)據(jù)結(jié)構(gòu)中的堆實(shí)質(zhì)上是滿足一定性質(zhì)的完全二叉樹：二叉樹中任一非葉子結(jié)點(diǎn)關(guān)鍵字的值均小于（大于）它的孩子結(jié)點(diǎn)的關(guān)鍵字。 在小根堆中，第一個元素（完全二叉樹的根結(jié)點(diǎn)）的關(guān)鍵字最小； 大根堆中，第一個元素（完全二叉樹的根結(jié)點(diǎn)）的關(guān)鍵字最大， 顯然，堆中任一子樹仍是一個堆。 假設(shè)，節(jié)點(diǎn)I是數(shù)組A中下標(biāo)為i的節(jié)點(diǎn)： 那么，節(jié)點(diǎn)I的父節(jié)點(diǎn)下標(biāo)為：（i-1）/2 節(jié)點(diǎn)I的左子節(jié)點(diǎn)下標(biāo)為：2 * i + 1 節(jié)點(diǎn)I的右子節(jié)點(diǎn)下標(biāo)為：2 * i + 2 詳細(xì)圖解如下存儲與邏輯表示 【3】堆存儲與邏輯結(jié)構(gòu)表示 如下圖所示：
注意：示例中的邏輯結(jié)構(gòu)堆不是最大堆也不是最小堆，僅僅只是為了便于理解堆的邏輯結(jié)構(gòu)。 【4】堆排序定義 n個關(guān)鍵字序列Kl，K2，…，Kn稱為堆，當(dāng)且僅當(dāng)該序列滿足如下性質(zhì)（簡稱為堆性質(zhì)）： （1) ki ≤ K2i 且 ki ≤ K2i+1 或 （2） Ki ≥ K2i 且 ki ≥ K2i+1（（i=1,2,…,[n/2]，其中[]表示上取整） 若將此序列所存儲的向量R[1..n]看做是一棵完全二叉樹的存儲結(jié)構(gòu)，則堆實(shí)質(zhì)上是滿足如下性質(zhì)的完全二叉樹： 樹中任一非葉結(jié)點(diǎn)的關(guān)鍵字均不大于（或不小于）其左右孩子（若存在）結(jié)點(diǎn)的關(guān)鍵字。 【5】堆排序思想 堆排序利用了大根堆(或小根堆)堆頂（根節(jié)點(diǎn)）記錄的關(guān)鍵字最大(或最小)這一特征，使得在當(dāng)前無序區(qū)中選取最大(或最小)關(guān)鍵字的記錄變得簡單。 （1）用大根堆排序的基本思想 <1>先將初始文件R[1.....N]建成一個大根堆，此堆為初始的無序區(qū)。 <2>再將關(guān)鍵字最大的記錄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ì)，故應(yīng)將當(dāng)前無序區(qū)R[1..n-1]調(diào)整為堆。 然后再次將R[1..n-1]中關(guān)鍵字最大的記錄R[1]和該區(qū)間的最后一個記錄R[n-1]交換 由此得到新的無序區(qū)R[1..n-2]和有序區(qū)R[n-1..n]，且仍滿足關(guān)系R[1..n-2].keys ≤ R[n-1..n].keys，同樣要將R[1..n-2]調(diào)整為堆。 直到無序區(qū)只有一個元素為止。 （2）大根堆排序算法的基本操作： <1> 初始化操作：將R[1..n]構(gòu)造為初始堆； <2>每一趟排序的基本操作：將當(dāng)前無序區(qū)的堆頂記錄R[1]和該區(qū)間的最后一個記錄交換，然后將新的無序區(qū)調(diào)整為堆(亦稱重建堆)。 注意： <1>只需做n-1趟排序，選出較大的n-1個關(guān)鍵字即可以使得文件遞增有序。 <2>用小根堆排序與利用大根堆類似，只不過其排序結(jié)果是遞減有序的。 堆排序和直接選擇排序相反：在任何時刻，堆排序中無序區(qū)總是在有序區(qū)之前，且有序區(qū)是在原向量的尾部由后往前逐步擴(kuò)大至整個向量為止。 （3）排序邏輯結(jié)構(gòu)演示如下圖所示：
請結(jié)合以上邏輯分析內(nèi)容或以下實(shí)現(xiàn)代碼加深對堆排序的理解。 【6】堆排序?qū)崿F(xiàn) （1）C++實(shí)現(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)整為最大堆結(jié)果如下："<<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<<"排序后結(jié)果如下："<<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)整為最大堆結(jié)果如下： 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 排序后結(jié)果如下： 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 } 堆排序的實(shí)現(xiàn)代碼有很多種實(shí)現(xiàn)方式，在此僅作為參考。 【7】堆排序分析 堆排序的時間，主要由建立初始堆和反復(fù)重建堆這兩部分的時間開銷構(gòu)成，它們均是通過調(diào)用堆調(diào)整函數(shù)實(shí)現(xiàn)的。 堆排序的最壞時間復(fù)雜度為O（nlgn）（參見隨筆《算法復(fù)雜度》）。堆排序的平均性能較接近于最壞性能。 由于建初始堆所需的比較次數(shù)較多，所以堆排序不適宜于記錄數(shù)較少的文件。 堆排序是就地排序，輔助空間為O（1）。 它是不穩(wěn)定的排序方法（參見隨筆《常用排序算法穩(wěn)定性分析》）。
Good Good Study, Day Day Up. 順序 選擇 循環(huán) 堅(jiān)持 總結(jié) |
|
|
