堆排序是一種樹形選擇排序，是對直接選擇排序的有效改進。
堆的構建--》堆排：
初始狀態-<從最后一個結點開始，使該子樹成堆（最小/大的數移到根節點）,不斷循環>-初始堆（小/大頂）--輸出堆頂元素（堆頂與堆的最后一個元素交換位置）--最后一個數移至堆頂--重新建--輸出堆頂元素
以下為《數據結構（C++版）習題解答與實驗指導》實例
1、算法思想
堆：具有n個元素的序列（k1,k2,...,kn),當且僅當滿足
時稱之為堆。由堆的定義可以看出，堆頂元素（即第一個元素）必為最小項（最大項）。
若以一維數組存儲一個堆，則堆對應一棵完全二叉樹，且所有非葉結點的值均不大于(或不小于)其子女的值，根結點（堆頂元素）的值是最小(或最大)的。如：
(a)大頂堆序列：（96, 83,27,38,11,09)
(b)小頂堆序列：（12，36，24，85，47，30，53，91）
初始時把要排序的n個數的序列看作是一棵順序存儲的二叉樹（一維數組存儲二叉樹），調整它們的存儲序，使之成為一個堆，將堆頂元素輸出，得到n 個元素中最小(或最大)的元素，這時堆的根節點的數最小（或者最大）。然后對前面(n-1)個元素重新調整使之成為堆，輸出堆頂元素，得到n 個元素中次小(或次大)的元素。依此類推，直到只有兩個節點的堆，并對它們作交換，最后得到有n個節點的有序序列。稱這個過程為堆排序。
因此，實現堆排序需解決兩個問題：
1. 如何將n 個待排序的數建成堆；
2. 輸出堆頂元素后，怎樣調整剩余n-1 個元素，使其成為一個新堆。
首先討論第二個問題：輸出堆頂元素后，對剩余n-1元素重新建成堆的調整過程。
調整大頂堆的方法：
1）設有m 個元素的堆，輸出堆頂元素后，剩下m-1 個元素。將堆底元素送入堆頂（（最后一個元素與堆頂進行交換），堆被破壞，其原因僅是根結點不滿足堆的性質。
2）將根結點與左、右子樹中較大元素的進行交換。
3）若與左子樹交換：如果左子樹堆被破壞，即左子樹的根結點不滿足堆的性質，則重復方法 （2）.
4）若與右子樹交換，如果右子樹堆被破壞，即右子樹的根結點不滿足堆的性質。則重復方法 （2）.
5）繼續對不滿足堆性質的子樹進行上述交換操作，直到葉子結點，堆被建成。
稱這個自 根結點 到 葉子結點 的調整過程為篩選。如圖：
再討論對n 個元素初始建堆的過程。
建堆方法：對初始序列建堆的過程，就是一個反復進行篩選的過程。
1）n 個結點的完全二叉樹，則最后一個結點是第
個結點的子樹。【向下取整】
2）篩選從第
個結點為根的子樹開始，該子樹成為堆。
3）之后向前依次對各結點為根的子樹進行篩選，使之成為堆，直到根結點。
如圖建堆初始過程：無序序列：（49，38，65，97，76，13，27，49）
2、代碼實現
~~~
package sort;
public class HeapSort {
public static void main(String[] args) {
int[] src = { 66, 89, 8, 123, 9, 44, 55, 37, 200, 127, 98 };
System.out.println("初始值：");
print(src);
HeapSort(src, src.length);
System.out.println("堆排后：");
print(src);
}
/**
* 大頂堆排序算法
*/
private static void HeapSort(int src[], int length) {// 大頂堆排序算法
// 初始化堆,從最后一個節點 i= (length-1) / 2
for (int i = (length - 1) >> 1; i >= 0; --i)
HeapAdjust(src, i, length);
for (int i = length - 1; i > 0; --i) {// 從堆尾往前調整
src[i] = src[0] + (src[0] = src[i]) * 0;// 彈出堆頂最大值，堆尾值填補
HeapAdjust(src, 0, i);// 重新調整堆
}
}
/**
* src[i+1,…. ,j]已經成堆，調整 i 的子樹為堆.
*
* @param src是待調整的堆數組
* @param i是待調整的數組元素的位置
* @param j是待調整數組的長度
*/
private static void HeapAdjust(int src[], int i, int j) {// 對下標為i的節點，調整其子樹為堆
int temp = src[i];
int child = 2 * i + 1; // 左孩子的位置。(child+1 為當前調整結點的右孩子的位置)
while (child < j) {// 防止第一次length為偶數12時，i=5與child=11非父子關系
if (child + 1 < j && src[child] < src[child + 1]) { // 定位較大的的孩子結點
++child;
}
if (src[i] < src[child]) { // 如果較大的子結點大于父結點
src[i] = src[child]; // 那么把較大的子結點往上移動，替換它的父結點
i = child; // 更新i，以便使新子樹為堆（子樹結構可能改變）
src[i] = temp; // 父結點放到比它大的孩子結點上（temp值未變）
child = 2 * i + 1;// 若child<length，則繼續循環建堆
} else { // 如果當前待調整結點大于它的左右孩子，則不需要調整，直接退出
break;// 防止死循環
}
}
print(src);
}
private static void print(int a[]) {
for (int i : a) {
System.out.print(i + " ");
}
System.out.println();
}
}
~~~
3、算法分析
堆排序也是一種不穩定的排序算法。?
堆排序優于簡單選擇排序的原因：
直接選擇排序中，為了從R[1..n]中選出關鍵字最小的記錄，必須進行n-1次比較，然后在R[2..n]中選出關鍵字最小的記錄，又需要做n-2次比較。事實上，后面的n-2次比較中，有許多比較可能在前面的n-1次比較中已經做過，但由于前一趟排序時未保留這些比較結果，所以后一趟排序時又重復執行了這些比較操作。
堆排序的**最壞時間復雜度為O(nlogn)**。堆序的平均性能較接近于最壞性能。由于建初始堆所需的比較次數較多，所以堆排序不適宜于記錄數較少的文件。因為其運行時間主要耗費在建初始堆和調整建新堆時進行的反復“篩選”上。
堆排序在最壞的情況下，其時間復雜度也為O(nlogn)。相對于快速排序來說，這是堆排序的最大優點。此外，堆排序僅需一個記錄大小的供交換用的輔助存儲空間。
建堆時對于每個非終端結點來說，其實最多進行兩次比較和互換操作，比較次數不超過4n 次，因此整個構建堆的時間復雜度為O(n)。
設樹深度為k
，從根到葉的篩選，元素比較次數至多2(k-1)次，交換記錄至多k 次。所以，在建好堆后，排序過程中的篩選次數不超過下式：
因此堆排序最壞情況下，**時間復雜度也為：O(nlogn )**。
4、算法改進
堆排序可通過樹形結構保存部分比較結果，可減少比較次數。
源碼地址：[https://github.com/zxiaofan/Algorithm/blob/master/src/sort/HeapSort.java](https://github.com/zxiaofan/Algorithm/blob/master/src/sort/HeapSort.java)
