堆排序算法及用C++實現(xiàn)基于最大堆的堆

　　還不知道堆排序算法是怎么計算的嗎？下面小編為大家整理了堆排序算法及用C++實現(xiàn)基于最大堆的堆，希望能幫到大家！

　　1、堆排序定義

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

　　(1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤ )

　　若將此序列所存儲的向量R[1..n]看做是一棵完全二叉樹的存儲結(jié)構(gòu)，則堆實質(zhì)上是滿足如下性質(zhì)的完全二叉樹：樹中任一非葉結(jié)點的關(guān)鍵字均不大于(或不小于)其左右孩子(若存在)結(jié)點的關(guān)鍵字。

　　【例】關(guān)鍵字序列(10，15，56，25，30，70)和(70，56，30，25，15，10)分別滿足堆性質(zhì)(1)和(2)，故它們均是堆，其對應(yīng)的完全二叉樹分別如最小堆示例和最大堆示例所示。

　　堆排序算法

　　2、最大堆和最小堆

　�。�1）根結(jié)點(亦稱為堆頂)的關(guān)鍵字是堆里所有結(jié)點關(guān)鍵字中最小者的堆稱為最小堆。

　　（2）結(jié)點(亦稱為堆頂)的關(guān)鍵字是堆里所有結(jié)點關(guān)鍵字中最大者，稱為最大堆。

　　注意：

　�。�1）堆中任一子樹亦是堆。

　�。�2）以上討論的堆實際上是二叉堆(Binary Heap)，類似地可定義k叉堆。

　　3、堆排序的基本思路如下:

　�。�1）把待排序數(shù)組構(gòu)造成一個最大堆

　　（2）取出樹的根(最大(小)值, 實際算法的實現(xiàn)并不是真正的取出)

　�。�3）將樹中剩下的元素再構(gòu)造成一個最大堆(這里的構(gòu)造和第1步不一樣，具體看實現(xiàn)部分)

　�。�4）重復(fù)2,3操作，直到取完所有的元素

　�。�5）把元素按取出的順序排列，即得到一個有序數(shù)組(在代碼實現(xiàn)里是通過交換操作"無形中"完成的)

　　在開始實現(xiàn)算法先看幾個結(jié)論(證明略):

　　（1）完全二叉樹A[0:n-1]中的任意節(jié)點，其下標(biāo)為 ii, 那么其子節(jié)點的下標(biāo)分別是為2i+12i+1 和 2(i+1)2(i+1)

　　（2）大小為n的完全二叉樹A[0:n-1]，葉子節(jié)點中下標(biāo)最小的是n2n2， 非葉子節(jié)點中下標(biāo)最大的是n21n21

　�。�3）如果數(shù)組是一個最大堆，那么最大元素就是A[0]

　　（4）最大堆中任意節(jié)點的左右子樹也是最大堆

　　4、實現(xiàn)示例

　　這里的算法實現(xiàn)使用的是最大堆，首先來解決由數(shù)組建立最大堆的問題:

　　// 用于計算下標(biāo)為i的節(jié)點的兩個子節(jié)點的下標(biāo)值#define LEFT(i) (2 * (i) + 1)#define RIGHT(i) (2 * ((i) + 1))   /* 此函數(shù)把一顆二叉樹中以node為根的子樹變成最大堆。 * 注意: 使用的前提條件是 node節(jié)點的左右子樹(如果存在的話)都是最大堆。 * 這個函數(shù)是整個算法的關(guān)鍵。 */void max_heapify(int heap[], int heap_size, int node){ // 這里先不考慮整數(shù)溢出的問題 // 先把注意力放在主要的功能上 // 如果數(shù)據(jù)規(guī)模夠大,int類型必然會溢出 int l_child = LEFT(node); int r_child = RIGHT(node); int max_value = node; if (l_child < heap_size && heap[l_child] > heap[max_value]) { max_value = l_child; } if (r_child < heap_size && heap[r_child] > heap[max_value]) { max_value = r_child; } if (max_value != node) { swap_val(heap + node, heap + max_value);  // 之后還要保證被交換的子節(jié)點構(gòu)成的子樹仍然是最大堆 // 如果不是這個節(jié)點會繼續(xù)"下沉"，直到合適的位置 max_heapify(heap, heap_size, max_value); }} /* 將一個數(shù)組構(gòu)造成最大堆 * 自底向上的利用max_heapify函數(shù)處理 */void build_max_heap(int heap[], int heap_size){ if (heap_size < 2) { return; } int first_leaf = heap_size >> 1;//第一個葉子節(jié)點的下標(biāo) int i; // 從最后一個非葉子節(jié)點開始自底向上構(gòu)建， // 葉子節(jié)點都看作最大堆，因此可以使用max_heapify函數(shù) for (i = first_leaf - 1; i >= 0; i--) { max_heapify(heap, heap_size, i); }}

　　函數(shù)max_heapify將指定子樹的根節(jié)點"下沉"到合適的位置, 最終子樹變成最大堆， 該過程最壞時間復(fù)雜度為O(logn)O(logn)。函數(shù)build_max_heap自底向上的調(diào)用max_heapify, 最終整個數(shù)組滿足最大堆，迭代過程的復(fù)雜度為O(nlogn)O(nlogn)， 因此整個函數(shù)的最壞時間復(fù)雜度也是O(nlogn)O(nlogn)。 而如果當(dāng)前數(shù)組已經(jīng)是最大堆了，例如數(shù)組原本是降序排列的， 那么max_heapify過程的時間復(fù)雜度就是O(1)O(1), 此時build_max_heap的時間復(fù)雜度是O(n)O(n)，這是最好的情況。

　　接著實現(xiàn)堆排序過程：

　　/* heap sort 主函數(shù) */void heap_sort(int heap[], int heap_size){ if (heap == NULL || heap_size < 2) { return; } //構(gòu)建最大堆 build_max_heap(heap, heap_size); int i; for (i = heap_size - 1; i > 0; i--) { /* 把當(dāng)前樹的根節(jié)點交換到末尾  * 相當(dāng)于取出最大值，樹的規(guī)模變小。  * 交換后的樹不是最大堆，但是根的兩顆子樹依然是最大堆  * 滿足調(diào)用max_heapify的條件。之所以這樣交換，  * 是因為用max_heapify處理時間復(fù)雜度較低，  * 如果不交換而直接"取出"heap[0], 此處可能要使用  * build_max_heap重新建立最大堆，時間復(fù)雜度較大  */ swap_val(heap, heap + i);  heap_size--; //維護(hù)最大堆 max_heapify(heap, heap_size, 0); }}

　　最終的堆排序算法中，build_max_heap的復(fù)雜度是已知的， 迭代部分和build_max_heap的實現(xiàn)類似，而且不難看出， 交換后的根元素在下一次建堆過程中必然下沉到堆底，因此無論情況好壞， 該迭代過程時間復(fù)雜度都是O(nlogn)O(nlogn)， 所以整個算法的最好最壞和平均時間復(fù)雜度都是O(nlogn)O(nlogn)。

　　堆排序算法的空間復(fù)雜度是O(1)O(1)，從實現(xiàn)上很容易看出來。

【堆排序算法及用C++實現(xiàn)基于最大堆的堆】相關(guān)文章：

java堆排序的算法思想的分析09-14

C++實現(xiàn)自底向上的歸并排序算法09-09

PHP實現(xiàn)抽獎概率算法09-13

權(quán)重隨機(jī)算法的java實現(xiàn)08-13

PID算法的C語言實現(xiàn)07-19

《算法及其實現(xiàn)》的備課教案09-12

用PHP基于Redis消息隊列實現(xiàn)發(fā)布微博的方法08-30

java通用組合算法如何實現(xiàn)09-12

JAVA簡單選擇排序算法及實現(xiàn)10-02

C語言中實現(xiàn)KMP算法實例08-09