原創公衆号： bigsai
前言
在個人的專欄中，其他排序陸陸續續都已經寫了，而堆排序遲遲沒有寫，現在把堆排序也寫一寫。
插入類排序—(折半)插入排序、希爾排序 交換類排序—冒泡排序、快速排序手撕圖解歸并類排序—歸并排序(逆序數問題) 計數排序引發的圍觀風波——一種O(n)的排序 兩分鐘搞懂桶排序
對于常見的快排、歸并這些O(nlogn)的排序算法，我想大部分人可能很容易搞懂，但是堆排序大部分人可能比較陌生，或許在Java的comparator接口中可能了解一點。但堆排序在應用中比如優先隊列此類維護動态資料效率比較高，有着非常廣泛的應用。
而堆排序可以拆分成堆和排序，其中你可能對堆比較陌生，對排序比較熟悉，下面就帶你徹底了解相關内容。
堆
什麼是堆？
談起堆，很多人第一聯想到的是土堆，而在資料結構中這種土堆與完全二叉樹更像，而堆就是一類特殊的資料結構的統稱。堆通常是一個可以被看做一棵樹(完全)的數組對象。且總是滿足以下規則：
- 堆總是一棵完全二叉樹
- 每個節點總是大于(或小于)它的孩子節點。
完全二叉樹
我想什麼是完全二叉樹大部分人也是知道：最後一層以上都是滿的，最後一層節點從左到右可以排列(有任何空缺即不滿足完全二叉樹)。
看作樹的數組對象
我們都知道我們排序的對象一般都是對數組之類的序列進行排序，如果轉成抽象資料結構再實作可能成本比較大。
我們正常在構造一棵二叉樹的時候通常采用鍊式left，right節點，但其實二叉樹的表示方式用數組也可以實作，隻不過普通的二叉樹如果用數組儲存可能空間利用 效率會很低而很少采用，但我們的堆是一顆完全二叉樹。使用數組儲存空間使用效率也比較高，是以在形式上我們把這個數組看成對應的完全二叉樹，而操作上可以直接操作數組也比較友善。
大根堆 VS 小根堆
上面還有一點就是在這個完全二叉樹中所有節點均大于(或小于)它的孩子節點，是以這裡就分為兩種情況
- 如果所有節點大于孩子節點值，那麼這個堆叫做大根堆，堆的最大值在根節點。
- 如果所有節點小于孩子節點值，那麼這個堆叫做小根堆，堆的最小值在根節點。
堆排序
通過上面的介紹，我想你對堆應該有了一定的認識，堆排序肯定是借助堆實作的某種排序，其實堆排序的整體思路也很簡單，就是
- 建構堆，取堆頂為最小(最大)。
- 将剩下的元素重新建構一個堆，取堆頂，一直到元素取完為止。
建堆
如果給一個無序的序列，首先要給它建成一個堆，我們如何實作這個操作呢？以下拿一個小根堆為例進行分析。
對于二叉樹(數組表示)，我們從下往上進行調整，從第一個非葉子節點開始向前調整，對于調整的規則如下：
①對于小根堆，目前節點與左右孩子比較，如果均小于左右孩子節點，那麼它本身就是一個小根堆，它不需要做任何改變，如果左右有孩子節點比它還小，那麼就要和最小的那個進行替換。
②但是普通節點替換可能沒問題，對于某些和子節點替換有可能改變子樹成堆，是以需要繼續往下判斷交換(最差判斷到葉子節點)。
分析構造堆的這個過程，每個非葉子節點都需要判斷比較是否交換，這樣一層就是O(n)，而每個節點可能替換之後影響子節點成堆需要再往下判斷周遊，你可能會認為它是一個O(nlogn),但其實你看看二叉樹性值，大部分都是在底部的，上面的隻有很少個數，如果你用數學方法去求得最終的複雜度它還是一個O(n)級别，這裡就不作詳細介紹了。
一個大根堆建立過程也是一樣的：
上面的一個堆建造完畢之後，我們怎麼去利用這個堆實作排序呢？答案也是很簡單的，我們知道堆有一個特性就是堆頂是最小(或最大)，而我們建造這個如果去除第一個元素，剩餘左右孩子依然滿足堆的性質。
将最後一個元素放置堆頂，由于第一個元素的存在使得整個不滿足堆的性質。分析這個結構，和我們前面構造堆的過程中構造到第一個元素的操作相同：
- 判斷左右孩子，如果需要交換則交換，交換後再次考慮交換子節點是否需要交換。一直到不需要考慮。
這樣到最後，堆排序即可完成，最終得到的序列即為堆排序序列。
一個大根堆的排序過程如下：
具體實作
有了上述的思想之後，如何具體的實作這個堆排序的代碼呢？
從細緻的流程來看，大概流程是如下的：
給定數組建堆(creatHeap)
- 從第一個非葉子節點開始判斷交換下移(shiftDown)，使得目前節點和子孩子能夠保持堆的性值
- 如果交換打破子孩子堆結構性質，那麼就要重新下移(shiftDown)被交換的節點一直到停止。
堆構造完成，取第一個堆頂元素為最小(最大)，剩下左右孩子依然滿足堆的性值，但是缺個堆頂元素，如果給孩子調上來，可能會調動太多并且可能破壞堆結構。
- 是以索性把最後一個元素放到第一位。這樣隻需要判斷交換下移(shiftDown）,不過需要注意此時整個堆的大小已經發生了變化，我們在邏輯上不會使用被抛棄的位置，是以在設計函數的時候需要附帶一個堆大小的參數。
- 重複以上操作，一直堆中所有元素都被取得停止。
而堆算法複雜度的分析上，之前建堆時間複雜度是O(n)。而每次删除堆頂然後需要向下交換，每個個數最壞為logn個。這樣複雜度就為O(nlogn).總的時間複雜度為O(n)+O(nlogn)=O(nlogn).
具體實作的代碼如下：
import java.util.Arrays;
public class 堆排序 {
static void swap(int arr[],int m,int n)
{
int team=arr[m];
arr[m]=arr[n];
arr[n]=team;
}
//下移交換 把目前節點有效變換成一個堆(小根)
static void shiftDown(int arr[],int index,int len)//0 号位置不用
{
int leftchild=index*2+1;//左孩子
int rightchild=index*2+2;//右孩子
if(leftchild>=len)
return;
else if(rightchild<len&&arr[rightchild]<arr[index]&&arr[rightchild]<arr[leftchild])//右孩子在範圍内并且應該交換
{
swap(arr, index, rightchild);//交換節點值
shiftDown(arr, rightchild, len);//可能會對孩子節點的堆有影響，向下重構
}
else if(arr[leftchild]<arr[index])//交換左孩子
{
swap(arr, index, leftchild);
shiftDown(arr, leftchild, len);
}
}
//将數組建立成堆
static void creatHeap(int arr[])
{
for(int i=arr.length/2;i>=0;i--)
{
shiftDown(arr, i,arr.length);
}
}
static void heapSort(int arr[])
{
System.out.println("原始數組為 ："+Arrays.toString(arr));
int val[]=new int[arr.length]; //臨時儲存結果
//step1建堆
creatHeap(arr);
System.out.println("建堆後的序列為 ："+Arrays.toString(arr));
//step2 進行n次取值建堆，每次取堆頂元素放到val數組中，最終結果即為一個遞增排序的序列
for(int i=0;i<arr.length;i++)
{
val[i]=arr[0];//将堆頂放入結果中
arr[0]=arr[arr.length-1-i];//删除堆頂元素，将末尾元素放到堆頂
shiftDown(arr, 0, arr.length-i);//将這個堆調整為合法的小根堆，注意(邏輯上的)長度有變化
}
//數值克隆複制
for(int i=0;i<arr.length;i++)
{
arr[i]=val[i];
}
System.out.println("堆排序後的序列為:"+Arrays.toString(arr));
}
public static void main(String[] args) {
int arr[]= {14,12,16,8,9,1,14,9,6 };
heapSort(arr);
}
}
執行結果：
當然，代碼為了成章節我把它命名為中文，還有些不規範的地方請注意甄别。
結語
對于堆排序就先介紹到這裡了，當然堆的強大之處不止這麼一點，優先隊列同樣也是用到堆但是這裡就不詳細介紹了，我相信優秀的你肯定又掌握了一門O(nlogn)級别的排序算法啦。如果寫的有啥不确切地方還請指正。
最後，如果感覺不錯一鍵三聯哦！，歡迎關注公衆号：
bigsai
,更多精彩等你來看。期待你的關注，并且筆者也準備了一波pdf學習資源分享給你。