< 排序大全系列 > 堆排序總結(jié)：
直觀動(dòng)圖理解：
算法知識(shí)導(dǎo)引：
-
什么是 “堆” ？：
堆是一種近似完全二叉樹的結(jié)構(gòu)，通常堆是通過(guò) 一維數(shù)組 來(lái)實(shí)現(xiàn)的。
二叉樹我們?cè)趯W(xué)離散數(shù)學(xué)的時(shí)候都見(jiàn)過(guò)，那具體什么是 完全二叉樹 呢？這個(gè)二叉樹應(yīng)該滿足一下兩個(gè)條件：
- 假設(shè)整個(gè)二叉樹深度為 n，那么除了第 n 層及其樹葉，其他各層的結(jié)點(diǎn)都達(dá)到了最大個(gè)數(shù)，有 2 個(gè)分叉
- 且第 n 層的樹葉全部集中在左側(cè)
從上到下以從大到小的關(guān)系形成的樹可以叫做 最大堆，反之就叫做 最小堆。
注意：以最大堆為例并不代表層數(shù)更高，數(shù)字就一定更大，二叉堆只需要滿足父結(jié)點(diǎn)比子結(jié)點(diǎn)大就可以了。
完全二叉樹如下圖所示：
-
那為什么可以用一維數(shù)組來(lái)表示，而不是單獨(dú)寫一個(gè) 完全二叉樹類呢？：
是因?yàn)橥耆鏄溆幸恍┆?dú)特的性質(zhì)：
就如上圖所示，我們的圈圈里現(xiàn)在還沒(méi)有裝數(shù)據(jù)，現(xiàn)在圈里的數(shù)字是序號(hào)。像這樣從上到下，從左到右地依次給完全二叉樹編號(hào)后，我們就可以根據(jù) 編號(hào)與結(jié)點(diǎn) 之間的微妙關(guān)系得出一些結(jié)論：
- n 號(hào)結(jié)點(diǎn)的下屬左結(jié)點(diǎn)的序號(hào)是 2n
- n 號(hào)結(jié)點(diǎn)的下屬右結(jié)點(diǎn)的序號(hào)是 2n+1
- n 號(hào)結(jié)點(diǎn)（只要它有父結(jié)點(diǎn)）的父結(jié)點(diǎn)序號(hào)為 n/2 ，注意是計(jì)算機(jī)的整數(shù)除法
我們通常從一個(gè)數(shù)組的 [ 1 ] 位置開(kāi)始填入值而不是 [ 0 ]。
接下來(lái)我們以最大堆為例，做一個(gè) C++ 的代碼實(shí)現(xiàn)：
#include <iostream> #include <algorithm> #include <cmath> #include <ctime> using namespace std; template<typename Item> class MaxHeap{ private: Item *data = NULL; int count; /* 有多少個(gè)有效的值 */ public: MaxHeap(int capacity){ /* capacity 容量 */ data = new Item[ capacity+1 ]; /* +1 是因?yàn)槭菑?[1] 開(kāi)始存放的，浪費(fèi)了一個(gè)小格間，要滿足原有那么多數(shù)據(jù)的需求，就得 +1 */ } ~MaxHeap(){ delete [] data; /* 析構(gòu)函數(shù)里，完成空間的清理 */ } int size(){ return count; } bool isEmpty(){ return count == 0; } } int main(){ MaxHeap<int> maxheap = MaxHeap<int>(100); /* 一定記得這里填入的 100 代表的是空間大小！*/ cout<< maxheap.size() << endl; return 0; } -
那么一個(gè)二叉堆需要包含什么操作呢？：
當(dāng)有一個(gè)新的元素需要填入的時(shí)候，我們需要 SHIFT UP 操作：
private: void shiftUp( int k ){ while( k > 1 && data[k/2] < data[k] ){ /* k = 1 時(shí)就是根結(jié)點(diǎn)了，已經(jīng)沒(méi)有父結(jié)點(diǎn)可以判斷了。*/ /* 第二個(gè)判斷是 比較父結(jié)點(diǎn)是否小于子結(jié)點(diǎn)，如果是，那么就把大的向上推，小的換下來(lái)。*/ swap( data[k/2], data[k]); /* swap()大家都會(huì)寫，就不再贅述 */ k /= 2; } } /* 之所以把 shiftUp 寫成是 private ，是因?yàn)橛脩魶](méi)有必要調(diào)用該函數(shù)。*/ public: void insert( Item item ){ data[count+1] = item; /* 在數(shù)組末尾，添加進(jìn)新的一個(gè)元素*/ ++ count; }當(dāng)我們需要取出一個(gè)元素的時(shí)候，我們必須要保證取出后，堆依然滿足自身需要的那些條件，所以需要 SHIFT DOWN 操作：
/* 格式基本同上：*/ private: void shitDown(){ while( 2*k <= count ){ int j = 2*k; // 在此輪循環(huán)中，data[k] 和 data[j]交換位置 if( j+1 <= count && data[j+1] > data[j]) j += 1; if( data[k] >= data[j] ){ break; } swap( data[k], data[j] ); k = j; } } public: Item extractMax(){ assert( count > 0 ); Item ret = data[1]; /* 把此時(shí)的頂部元素保存下來(lái) 作為返回值*/ swap( data[1] , data[count] ); count --; shiftDown(1); /* 用最末的元素來(lái) shiftDown 一遍整個(gè)二叉堆，達(dá)到維護(hù)的效果。*/ return ret; }
那么接下來(lái)，我們就要正式開(kāi)始實(shí)現(xiàn) 堆排序 了：我們給出了兩種實(shí)現(xiàn)：
-
第一種是將 所需要排序的 arr[] 數(shù)組的元素 通過(guò) insert() 函數(shù)一個(gè)一個(gè)填入堆中：
代碼如下：
template<typename> void heapSort(T arr[], int n){ MaxHeap<T> maxheap = MaxHeap<T>(n); for( int i =0; i<n ; i ++){ maxheap.insert(arr[i]); } for( int i = n-1; i>=0 ; i--){ /* 這里展示的是 從小到大的順序，當(dāng)然如果想改為從大到小的話，本來(lái)每次 extractMax() 就是取出最大值，那么改為 初始化 i = 0 就好了*/ arr[i] = maxheap.extractMax(); } } -
第二種，是在構(gòu)造函數(shù)層面完成的，將 arr[] 數(shù)組傳入 MaxHeap 類中
代碼如下：
首先先需要在原 MaxHeap 類內(nèi)添加一個(gè)新的構(gòu)造函數(shù)： public: MaxHeap(Item arr[], int n){ data = new Item[ n+1 ]; capacity = n; for( int i=0; i<n ; i++ ) data[i+1] = arr[i]; count = n; for( int i = count/2 ; i>=1 ; i-- ){ shiftDown(i); } }我們是從最后一個(gè)葉子節(jié)點(diǎn)開(kāi)始進(jìn)行 shiftDown 操作，而在實(shí)際情況中，其實(shí)真正移動(dòng)了的元素并不多，這樣大大提高了效率，比一個(gè)一個(gè)地插入要好很多。
template<typename> void heapifySort(T arr[], int n){ MaxHeap<T> maxheap = MaxHeap<T>(arr, n); for( int i = n-1; i>=0 ; i--){ arr[i] = maxheap.extractMax(); } }
下面我們來(lái)看看經(jīng)過(guò)測(cè)試后的結(jié)果：
Test For Radom Array, size = 1000000, radom range [0, 1000000]:
heapSort Time: 0.616283s
heapify Time: 0.573522s
--------------------------------
Test For Radom Nearly Ordered Array, size = 1000000, radom range [0, 1000000]:
heapSort Time: 0.620693s
heapify Time: 0.341337s
--------------------------------
Test For Radom Array, size = 1000000, radom range [0, 10]:
heapSort Time: 0.361128s
heapify Time: 0.322639s
--------------------------------
Heapify 的算法復(fù)雜度比較：
將n個(gè)元素逐個(gè)插入到一個(gè)空堆中，算法復(fù)雜度是 O( nlogn )，
heapifySort 的過(guò)程，算法復(fù)雜度是 O( n )。
值得改進(jìn)的地方 —— 原地堆排序
我們上面的兩個(gè)算法都有一個(gè)問(wèn)題，那就是都需要新開(kāi)辟一個(gè)數(shù)組，然后有序地填入值來(lái)形成一個(gè)有序數(shù)組。
可是這樣的算法顯然是不夠好的，能不能就在原地空間內(nèi)，將數(shù)據(jù)整合有序呢？
思路是這樣的：
-
通過(guò)剛才新的 MaxHeap 的構(gòu)造函數(shù)，可以讓一個(gè)數(shù)組成為一個(gè)最大堆，那么假如有一個(gè) max 指針，指向的一定是該數(shù)組的第一項(xiàng)。
Step 1此時(shí)我們把它移到最末尾，那么此時(shí) 上圖中的 v 找到了最合適的位置，因?yàn)樗亲畲笾?，所以放在了最末尾?/p>
Step 2但此時(shí)，w已經(jīng)不是最大值，前面從 [ 0 ] 到 倒數(shù)第二個(gè) 元素之間，就不再是一個(gè)最大堆 Max Heap 了。所以我們對(duì) w 執(zhí)行一次 shiftDown 操作，使得橙色部分重新成為一個(gè) 最大堆。
Step 3那么第一個(gè)元素又是該最大堆中相對(duì)的最大值了，所以繼續(xù)甩到末尾排列。
Step 4
如此遞歸往復(fù)，就可以在原有數(shù)組內(nèi)，完成原地的堆排序。
各項(xiàng)指標(biāo)：
分類 -------------- 內(nèi)部比較排序
數(shù)據(jù)結(jié)構(gòu) ---------- 數(shù)組
最差時(shí)間復(fù)雜度 ---- O(nlogn)
最優(yōu)時(shí)間復(fù)雜度 ---- O(nlogn)
平均時(shí)間復(fù)雜度 ---- O(nlogn)
所需輔助空間 ------ O(1)
穩(wěn)定性 ------------ 不穩(wěn)定
堆排序是不穩(wěn)定的排序算法，不穩(wěn)定發(fā)生在堆頂元素與A[i]交換的時(shí)刻。
比如序列：{ 9, 5, 7, 5 }，堆頂元素是9，堆排序下一步將9和第二個(gè)5進(jìn)行交換，得到序列 { 5, 5, 7, 9 }，再進(jìn)行堆調(diào)整得到{ 7, 5, 5, 9 }，重復(fù)之前的操作最后得到{ 5, 5, 7, 9 }從而改變了兩個(gè)5的相對(duì)次序。
參考資料：
-
https://www.bilibili.com/video/av23849333/?p=1
數(shù)據(jù)結(jié)構(gòu)與算法之堆(完整版) （主要是 p1 和 p6 ）Blibili uploader：Python空間
-
https://www.cnblogs.com/eniac12/p/5329396.html#s4
CSDN精品博客文章：常用排序算法總結(jié)(一) Posted on 2016-03-28 22:13
