二叉堆（Binary Heap）是一顆特殊的完全二叉樹，一般分為大頂堆和小頂堆，我就不囉嗦啦！具體內容你可以看一下 圖解：什麼是二叉堆？
堆排序要學習今天的堆排序（Heap Sort），我們以一個數組 arr = [5、1、4、2、8、4] 開始（這個數組我們之前講排序算法常用的）：
我們首先以這個數組建立一個大頂堆，插入結點 5 作為根結點：
然後將結點 1 插入到最後一個位置，也就是結點 5 的左孩子，1 < 5 ，滿足大頂堆的屬性：
將結點 4 插入到最後一個位置，即結點 5 的右孩子 ，又因為 4 < 5 ，滿足大頂堆的屬性，不需要進行調整：
將結點 2 插入到最後一個位置，即結點 1 的左孩子位置，但是此時不滿足大頂堆的屬性（插入結點 2 小於其父結點 1 的值），所以交換兩者的值；此時並未結束，繼續判斷此時插入結點 2 與當前父結點 5 的大小關係，發現 2 < 5 ，滿足大頂堆的屬性，結束判斷。這個過程就是二叉堆的插入操作：
緊接著將結點 8 插入到最後一個位置，即結點 2 的右孩子位置，此時不滿足大頂堆的屬性（插入結點 8 小於其父結點 2 ），故交換兩者位置；然後繼續向上修正，判斷當前結點 8 與其父結點 5 的大小關係，8 > 5 （不滿足大頂堆的屬性），交換兩者位置，繼續修正，發現結點 8 已為樹的根結點，修正結束：
最後，我們將結點 4 插入到最後一個位置，即結點 4（下標為2） 的左孩子位置，且其值小於等於父結點，故不進行修正：
以上算是對於二叉堆插入操作的一個回顧，建堆的過程（這裡是按照插入操作進行建堆的），接下來才是堆排序的核心操作。
設
第一步：將堆頂的元素 8 （即數組 arr[0] ，最大元素）的元素與堆的最後一個元素 4（即數組當中的最後一個元素 4 ）交換，此時就相當於選擇出了數組當中的最大元素，將其從堆中去掉：
第二步：從結點 4 （下標為 0 ）開始進行 堆化（Heapify）操作，這裡我們只囉嗦一次奧！計算結點 4 （下標為 0 ）的左孩子
第三步：將堆頂元素 5 （下標為 0）和當前最後一個元素 2 （即 i 指向的位置）交換， 此時就相當於選擇出了數組當中的次最大元素，將其從堆中去掉：
第四步：從當前的堆頂元素 2 開始進行堆化操作，交換 2 （下標 0）和其左孩子 4 （下標 1），為什麼不是右孩子 4 （下標 2）呢？因為我們在堆化的時候，優先和左孩子進行了對比，只有當右孩子大於左孩子的情況下，才考慮將右孩子與其父結點交換，堆化後的結果如下圖所示：
第五步：交換根結點 4 和最後一個結點 1 ，從堆中去掉結點 4 （下標 3）：
第六步：從根結點 1 開始進行堆化操作，交換了根結點 1 和 4 （下標 2）：
第七步：交換根結點 4 和 1 ，從堆中去掉結點 4 ：
第八步：從根結點 1 開始進行堆化操作，交換了結點 2 和 1 ：
第九步：交換根結點 2 和最後一個元素 1 ，將結點 2 從堆中去掉：
第十步：發現堆中僅剩餘一個元素，堆排序結束，我們看到原始的輸入數組 arr = [5、1、4、2、8、4] 變成了有序數組 arr = [1、2、4、4、5、8] 。
這就是有趣有好玩的堆排序，其本質上是對二叉堆的一個應用。
我們都知道選擇排序是利用線性的時間複雜度
而堆排序事實上就是對選擇排序的一個優化，本來用
不難發現，堆排序是一個基於比較的排序算法，且在排序過程中由於要進行堆化操作（不斷交換）（Heapify），而造成其不穩定性，所以堆排序是一個不穩定的排序算法。
實現代碼只要會寫二叉堆的堆化操作，看堆排序的代碼會相當簡單。
public class HeapSort
{
public void heapSort(int arr[])
{
int n = arr.length;
//建堆（你也可以考慮進行上面的插入操作）但是這裡調用的是Heapify
//可以達到同樣的建堆效果
for (int i = n / 2 - 1; i >= 0; i--){
heapify(arr, n, i);
}
//從堆中一個一個地選擇出最大元素
for (int i = n-1; i > 0; i--)
{
// 交換堆的根結點(最大元素)與當前最後一個元素(i)
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// 在去掉最後一個元素的堆上進行堆化操作
heapify(arr, i, 0);
}
}
// 堆化操作
void heapify(int arr[], int n, int i)
{
int largest = i; // 初始化最大元素為根結點
int l = 2*i + 1; // i 的左孩子結點 left = 2*i + 1
int r = 2*i + 2; // i 的右孩子結點 right = 2*i + 2
// 如果左孩子結點比根結點大，更新largest為左孩子
if (l < n && arr[l] > arr[largest])
largest = l;
// 如果右孩子比最大元素大，更新largest為右孩子
if (r < n && arr[r] > arr[largest])
largest = r;
// 如果最大元素不是根結點，進行交換操作並遞歸調用Heapify
if (largest != i)
{
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
// 對由於交換操作受到影響的子樹遞歸調用Heapify
heapify(arr, n, largest);
}
}
public static void main(String args[])
{
int arr[] = {5,1,4,2,8,4};
int n = arr.length;
HeapSort ob = new HeapSort();
ob.sort(arr);
for(int i = 0; i < n; i++){
System.out.print(arr[i] + ",")
}
}
}請注意：上面代碼中的建堆操作代碼
for (int i = n / 2 - 1; i >= 0; i--){
heapify(arr, n, i);
}如果看這個代碼感覺不舒服，沒關係，我們用更香的方式來一遍。我們還是以數組 arr = [5、1、4、2、8、4] 為例說明這種建堆方式。
與插入操作建堆不同的是（插入操作建堆將原數組當做一個普通的數組），我們將數組 arr[] 從一開始就當做一顆完全二叉樹：
然後計算 i = 6/2 - 1 = 2 ，對結點 4（2） 應用堆化操作，發現大於等於其左孩子 4（5） 的值（其中括號中的數字表示下標）：
i-- ，i = 1 ，對結點 1（1） 應用堆化操作，計算其左孩子結點 2（3） ，右孩子結點 8（4） ，比較三者大小，發現結點 1（1） 的左右孩子均比其大，將最大結點 8（4） 和 1（1） 交換，此時 1（1） 已經到葉子結點了：
i-- = 0 ，對結點 5（0） 應用堆化操作，發現左孩子 8（3） 比其大，交換兩者，繼續對 5（3） 進行堆化，發現左右孩子均比其小，堆化結束：
這樣我們就得到了一個大頂堆。
for (int i = n / 2 - 1; i >= 0; i--){
heapify(arr, n, i);
}一個更有意思的問題來了，那你知道剛才講的 建堆時間複雜度是多少呢？
咋一看，這還不簡單，每次調用 Heapify() 函數的時間複雜度為
雖然上面的建堆操作的時間複雜度的上限
Heapify() 函數的運行時間取決於樹的高度
建堆的循環是從倒數第一層的結點
要想準確計算出建堆的時間複雜度，就必須知道對於高度為
這裡就要告訴大家一個不爭的事實啦，對於一個大小為
那麼建堆的時間複雜度就好算了，對於高度為
已知：
那麼：
因此，建立一個二叉堆的時間複雜度為
證明建立一個二叉堆的時間複雜度對於學習堆排序似乎沒有特別的意義，但希望考研、學習高等數學的朋友看到數學的魅力，還有數據結構的算法複雜度細究其實還是很有趣的。
祝你們周末愉快！記得點讚奧
推薦閱讀：
圖解「歸併排序」算法（修訂版）
圖解：什麼是快速排序？
漫畫：什麼是計數排序？
作者：景禹，一個追求極致的共享主義者，想帶你一起擁有更美好的生活，化作你的一把傘。