卷起來，淺析堆排序算法！
一、算法描述
是一顆完全二叉樹（Complete Binary Tree）
堆上面的每一個(gè)節(jié)點(diǎn)都必須滿足父結(jié)點(diǎn)的值大于等于子結(jié)點(diǎn)的值或者父結(jié)點(diǎn)的值小于等于子結(jié)點(diǎn)的值 。parent >= children or parent <= children
二、完全二叉樹
三、大頂堆和小頂堆
四、堆的性質(zhì)
例如我們已經(jīng)有一個(gè)大頂堆，那么這個(gè)大頂堆具有哪些特征呢？
將其映射為數(shù)組：
int arr[] = {12,10,9,6,7,8,5,3,2}
我們假設(shè)結(jié)點(diǎn) 6 的位置為 i = 3。那么我們可以求出，他的父節(jié)點(diǎn)和兩個(gè)子結(jié)點(diǎn)。
Parent =?( i - 1 )? /? 2，等于位置為 1 的結(jié)點(diǎn) 10。
C1 = 2i + 1，等于位置為 7 的結(jié)點(diǎn) 3 。
C2 = 2i + 2，等于位置為 8 的結(jié)點(diǎn) 2 。
五、圖解堆排序算法
我們以 int tree[] = {6, 10, 3, 8, 5, 12, 7, 2, 9} 為例，對堆排序的執(zhí)行過程進(jìn)行圖解。
第一步：通過原始序列構(gòu)造一個(gè)大頂堆（升序采用大頂堆，降序采用小頂堆）。
1. 先通過序列通過從上到下從左往右的順序構(gòu)造一個(gè)完全二叉樹。
2.? 對第三層的父節(jié)點(diǎn)和第四層的子結(jié)點(diǎn)進(jìn)行調(diào)整，其中粉紅色代表發(fā)生交換的結(jié)點(diǎn)。使得其父節(jié)點(diǎn)大于兩個(gè)子結(jié)點(diǎn)。
即也是從最后 1 個(gè)非葉子結(jié)點(diǎn)開始 (8 - 1) / 2 = 3, 也就是從 8 開始進(jìn)行從左到右從下到上進(jìn)行調(diào)整。
[8,2,9]?中，9 最大，交換 8 和 9。
3. 對第二層父節(jié)點(diǎn)和第三層子結(jié)點(diǎn)進(jìn)行調(diào)整。
[10,9,5]?中，10?最大，不交換。
[3,12,7]?中，12 最大，交換 3 和 12。
4. 對第一層父節(jié)點(diǎn)和第二層子結(jié)點(diǎn)進(jìn)行調(diào)整。
[6,10,12]?中，12 最大，交換 6 和 12。
這時(shí)，上面操作導(dǎo)致?[6,3,7]?不是一個(gè)大頂堆，繼續(xù)調(diào)整。
[6,3,7]?中，7 最大，交換 6 和 7。
至此，大頂堆構(gòu)建完成。
第二步：將根結(jié)點(diǎn)調(diào)整到最后一個(gè)位置，使末尾元素最大。然后對剩下元素繼續(xù)調(diào)整堆，根結(jié)點(diǎn)調(diào)整到最后一個(gè)位置，得到第二大元素。如此反復(fù)進(jìn)行交換、重夠、交換。
1. 將根節(jié)點(diǎn)元素 12 跟 8 交換。
2. 重新調(diào)整結(jié)構(gòu)，使其繼續(xù)滿足堆定義。
3. 將根節(jié)點(diǎn)元素 10 跟 2 交換。
4. 重新調(diào)整結(jié)構(gòu)，使其繼續(xù)滿足堆定義。
這樣一直交換、重夠、交換下去.......
5.最后一次將根節(jié)點(diǎn)元素 3 跟 2 交換。
這樣所有元素就達(dá)到了有序狀態(tài)。
六、算法實(shí)現(xiàn)
第一步：構(gòu)建大頂堆
#include?
void?swap(int?arr[], int?i, int?j){
??int?temp = arr[i];
??arr[i] = arr[j];
??arr[j] = temp;
}
void?heapify(int?tree[], int?n, int?i){
??if?(i >= n){
????return;
??}
??
??int?c1 = 2?* i + 1;
??int?c2 = 2?* i + 2;
??int?max = i;
??if?(c1 < n && tree[c1] > tree[max]){
????max = c1;
??}
??if?(c2 < n && tree[c2] > tree[max]){
????max = c2;
??}
??if?(max != i){
????swap(tree, max ,i);
????heapify(tree, n, max);
??}
}
void?build_heap(int?tree[], int?n){
??int?last_node = n - 1;
??int?parent = (last_node - 1) / 2;
??for?(int?i = parent; i >= 0; i--){
????heapify(tree, n, i);
??}
}
void?heap_sort(int?tree[], int?n){
??build_heap(tree, n);
??for?(int?i = n - 1; i >= 0; i--){
????swap(tree, i, 0);
????heapify(tree, i, 0);
??}
}
int?main(){
??int?tree[] = {6, 10, 3, 9, 5, 12, 7, 2, 8};
??int?n = 9;
??
??build_heap(tree, 9);
// heap_sort(tree, 9);
??
??for(int?i = 0; i < n; i++){
????printf("%d\n",tree[i]);
??}
??return?0;
}
輸出：
我們將它畫出來康康：
第二步：排序
#include?
void?swap(int?arr[], int?i, int?j){
??int?temp = arr[i];
??arr[i] = arr[j];
??arr[j] = temp;
}
void?heapify(int?tree[], int?n, int?i){
??if?(i >= n){
????return;
??}
??
??int?c1 = 2?* i + 1;
??int?c2 = 2?* i + 2;
??int?max = i;
??if?(c1 < n && tree[c1] > tree[max]){
????max = c1;
??}
??if?(c2 < n && tree[c2] > tree[max]){
????max = c2;
??}
??if?(max != i){
????swap(tree, max ,i);
????heapify(tree, n, max);
??}
}
void?build_heap(int?tree[], int?n){
??int?last_node = n - 1;
??int?parent = (last_node - 1) / 2;
??for?(int?i = parent; i >= 0; i--){
????heapify(tree, n, i);
??}
}
void?heap_sort(int?tree[], int?n){
??build_heap(tree, n);
??for?(int?i = n - 1; i >= 0; i--){
????swap(tree, i, 0);
????heapify(tree, i, 0);
??}
}
int?main(){
??int?tree[] = {6, 10, 3, 9, 5, 12, 7, 2, 8};
??int?n = 9;
??
// build_heap(tree, 9);
??heap_sort(tree, 9);
??
??for(int?i = 0; i < n; i++){
????printf("%d\n",tree[i]);
??}
??return?0;
}
輸出：
我們將它畫出來康康：
就這樣我們就完成堆排序啦！開不開森。
六、算法分析
時(shí)間復(fù)雜度：堆排序包括建堆和排序兩個(gè)操作，建堆過程的時(shí)間復(fù)雜度是 O(n)，排序過程的時(shí)間復(fù)雜度是 O(nlogn)，所以，堆排序整體的時(shí)間復(fù)雜度是 O(nlogn)。
空間復(fù)雜度：?因?yàn)槎雅判蚴蔷偷嘏判?，空間復(fù)雜度為常數(shù)：O(1)
穩(wěn)定性：不穩(wěn)定。因?yàn)樵诙训恼{(diào)整過程中，元素進(jìn)行比較和交換所走的是該結(jié)點(diǎn)到葉子結(jié)點(diǎn)的一條路徑，因此對于相同的元素就可能出現(xiàn)排在后面的元素被交換到前面來的情況。?
七、適用場景
堆排序在建立堆和調(diào)整堆的過程中會(huì)產(chǎn)生比較大的開銷，在元素少的時(shí)候并不適用。但是，在元素比較多的情況下，還是不錯(cuò)的一個(gè)選擇。尤其是在解決諸如“前n大的數(shù)”一類問題時(shí)，幾乎是首選算法。
