堆排序算法及用C++實(shí)現(xiàn)基于最大堆的堆
還不知道堆排序算法是怎么計(jì)算的嗎？下面小編為大家整理了堆排序算法及用C++實(shí)現(xiàn)基于最大堆的堆，希望能幫到大家！
1、堆排序定義
n個(gè)關(guān)鍵字序列Kl，K2，…，Kn稱為堆，當(dāng)且僅當(dāng)該序列滿足如下性質(zhì)(簡(jiǎn)稱為堆性質(zhì))：
(1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤ )
若將此序列所存儲(chǔ)的向量R[1..n]看做是一棵完全二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，則堆實(shí)質(zhì)上是滿足如下性質(zhì)的完全二叉樹(shù)：樹(shù)中任一非葉結(jié)點(diǎn)的關(guān)鍵字均不大于(或不小于)其左右孩子(若存在)結(jié)點(diǎn)的關(guān)鍵字。
【例】關(guān)鍵字序列(10，15，56，25，30，70)和(70，56，30，25，15，10)分別滿足堆性質(zhì)(1)和(2)，故它們均是堆，其對(duì)應(yīng)的完全二叉樹(shù)分別如最小堆示例和最大堆示例所示。
堆排序算法
2、最大堆和最小堆
（1）根結(jié)點(diǎn)(亦稱為堆頂)的關(guān)鍵字是堆里所有結(jié)點(diǎn)關(guān)鍵字中最小者的堆稱為最小堆。
（2）結(jié)點(diǎn)(亦稱為堆頂)的關(guān)鍵字是堆里所有結(jié)點(diǎn)關(guān)鍵字中最大者，稱為最大堆。
注意：
（1）堆中任一子樹(shù)亦是堆。
（2）以上討論的堆實(shí)際上是二叉堆(Binary Heap)，類似地可定義k叉堆。
3、堆排序的基本思路如下:
（1）把待排序數(shù)組構(gòu)造成一個(gè)最大堆
（2）取出樹(shù)的根(最大(小)值, 實(shí)際算法的實(shí)現(xiàn)并不是真正的取出)
（3）將樹(shù)中剩下的元素再構(gòu)造成一個(gè)最大堆(這里的構(gòu)造和第1步不一樣，具體看實(shí)現(xiàn)部分)
（4）重復(fù)2,3操作，直到取完所有的元素
（5）把元素按取出的順序排列，即得到一個(gè)有序數(shù)組(在代碼實(shí)現(xiàn)里是通過(guò)交換操作"無(wú)形中"完成的)
在開(kāi)始實(shí)現(xiàn)算法先看幾個(gè)結(jié)論(證明略):
（1）完全二叉樹(shù)A[0:n-1]中的任意節(jié)點(diǎn)，其下標(biāo)為 ii, 那么其子節(jié)點(diǎn)的下標(biāo)分別是為2i+12i+1 和 2(i+1)2(i+1)
（2）大小為n的完全二叉樹(shù)A[0:n-1]，葉子節(jié)點(diǎn)中下標(biāo)最小的是n2n2， 非葉子節(jié)點(diǎn)中下標(biāo)最大的是n21n21
（3）如果數(shù)組是一個(gè)最大堆，那么最大元素就是A[0]
（4）最大堆中任意節(jié)點(diǎn)的左右子樹(shù)也是最大堆
4、實(shí)現(xiàn)示例
這里的算法實(shí)現(xiàn)使用的是最大堆，首先來(lái)解決由數(shù)組建立最大堆的問(wèn)題:
/pic/* 此函數(shù)把一顆二叉樹(shù)中以node為根的子樹(shù)變成最大堆。 * 注意: 使用的前提條件是 node節(jié)點(diǎn)的左右子樹(shù)(如果存在的話)都是最大堆。 * 這個(gè)函數(shù)是整個(gè)算法的關(guān)鍵。 */void max_heapify(int heap[], int heap_size, int node){ /pic/pic/pic/pic/pic/* 將一個(gè)數(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;/pic/pic/pic/p>
函數(shù)max_heapify將指定子樹(shù)的根節(jié)點(diǎn)"下沉"到合適的位置, 最終子樹(shù)變成最大堆， 該過(guò)程最壞時(shí)間復(fù)雜度為O(logn)O(logn)。函數(shù)build_max_heap自底向上的調(diào)用max_heapify, 最終整個(gè)數(shù)組滿足最大堆，迭代過(guò)程的復(fù)雜度為O(nlogn)O(nlogn)， 因此整個(gè)函數(shù)的最壞時(shí)間復(fù)雜度也是O(nlogn)O(nlogn)。 而如果當(dāng)前數(shù)組已經(jīng)是最大堆了，例如數(shù)組原本是降序排列的， 那么max_heapify過(guò)程的時(shí)間復(fù)雜度就是O(1)O(1), 此時(shí)build_max_heap的時(shí)間復(fù)雜度是O(n)O(n)，這是最好的情況。
接著實(shí)現(xiàn)堆排序過(guò)程：
/* heap sort 主函數(shù) */void heap_sort(int heap[], int heap_size){ if (heap == NULL || heap_size < 2) { return; } /pic/* 把當(dāng)前樹(shù)的根節(jié)點(diǎn)交換到末尾 * 相當(dāng)于取出最大值，樹(shù)的規(guī)模變小。 * 交換后的樹(shù)不是最大堆，但是根的兩顆子樹(shù)依然是最大堆 * 滿足調(diào)用max_heapify的條件。之所以這樣交換， * 是因?yàn)橛胢ax_heapify處理時(shí)間復(fù)雜度較低， * 如果不交換而直接"取出"heap[0], 此處可能要使用 * build_max_heap重新建立最大堆，時(shí)間復(fù)雜度較大 */ swap_val(heap, heap + i); heap_size--; /pic/p>
最終的堆排序算法中，build_max_heap的復(fù)雜度是已知的， 迭代部分和build_max_heap的實(shí)現(xiàn)類似，而且不難看出， 交換后的根元素在下一次建堆過(guò)程中必然下沉到堆底，因此無(wú)論情況好壞， 該迭代過(guò)程時(shí)間復(fù)雜度都是O(nlogn)O(nlogn)， 所以整個(gè)算法的最好最壞和平均時(shí)間復(fù)雜度都是O(nlogn)O(nlogn)。
堆排序算法的空間復(fù)雜度是O(1)O(1)，從實(shí)現(xiàn)上很容易看出來(lái)。
【堆排序算法及用C++實(shí)現(xiàn)基于最大堆的堆】相關(guān)文章：
C++實(shí)現(xiàn)一維向量旋轉(zhuǎn)算法10-17
java堆排序的算法思想的分析11-29
C++實(shí)現(xiàn)自頂向下的歸并排序算法12-21
C++實(shí)現(xiàn)自底向上的歸并排序算法03-14
內(nèi)部排序之堆排序的實(shí)現(xiàn)02-21
C#排序算法之堆排序11-16
Java基于余弦方法實(shí)現(xiàn)的計(jì)算相似度算法示例02-10
C++選擇排序算法實(shí)例02-25