在學習堆排序之前，首先需要了解堆的含義：在含有 n 個元素的序列中，如果序列中的元素滿足下面其中一種關系時，此序列可以稱之為
堆
。
- ki ≤ k2i 且 ki ≤ k2i+1（在 n 個記錄的範圍内，第 i 個關鍵字的值小于第 2i 個關鍵字，同時也小于第 2i+1 個關鍵字）
- ki ≥ k2i 且 ki ≥ k2i+1（在 n 個記錄的範圍内，第 i 個關鍵字的值大于第 2i 個關鍵字，同時也大于第 2i+1 個關鍵字）
對于堆的定義也可以使用
完全二叉樹
來解釋，因為在完全二叉樹中第 i 個結點的左孩子恰好是第 2i 個結點，右孩子恰好是 2i+1 個結點。如果該序列可以被稱為堆，則使用該序列建構的完全二叉樹中，每個根結點的值都必須不小于（或者不大于）左右孩子結點的值。
以無序表 {49，38，65，97，76，13，27，49} 來講，其對應的堆用完全二叉樹來表示為：
圖 3 無序表對應的堆
提示：堆用完全二叉樹表示時，其表示方法不唯一，但是可以确定的是樹的根結點要麼是無序表中的最小值，要麼是最大值。
堆排序的原理
堆排序的
基本思想
是：通過将無序表轉化為堆，可以直接找到表中最大值或者最小值，然後将其提取出來，令剩餘的記錄再重建一個堆，取出次大值或者次小值，如此反複執行就可以得到一個有序序列，此過程為堆排序。
堆排序過程的代碼實作需要解決兩個問題：
- 如何将得到的無序序列轉化為一個堆；
- 在輸出堆頂元素之後（完全二叉樹的樹根結點），如何調整剩餘元素建構一個新的堆。
首先先解決第 2 個問題。圖 3 所示為一個完全二叉樹，若去除堆頂元素，即删除二叉樹的樹根結點，此時用二叉樹中最後一個結點 97 代替，如下圖所示：
此時由于結點 97 比左右孩子結點的值都大，破壞了堆的結構，是以需要進行調整：首先以堆頂元素 97 同左右子樹比較，同值最小的結點交換位置，即 27 和 97 交換位置：
由于替代之後破壞了根結點右子樹的堆結構，是以需要進行和上述一樣的調整，即令 97 同 49 進行交換位置：
通過上述的調整，之前被破壞的堆結構又重建立立。從根結點到葉子結點的整個調整的過程，被稱為“
篩選
”。
解決第一個問題使用的就是不斷篩選的過程，如下圖所示，無序表 {49，38，65，97，76，13，27，49} 初步建立的完全二叉樹，如下圖所示：
在對上圖做篩選工作時，
規律
是從底層結點開始，一直篩選到根結點。對于具有 n 個結點的完全二叉樹，篩選工作開始的結點為第
⌊n/2⌋
個結點（此結點後序都是葉子結點，無需篩選）。
是以，對于有 8 個結點的完全二叉樹，篩選工作從第 4 個結點 97 開始，由于 97 > 49 ,是以需要互相交換，交換後如下圖所示：
然後再篩選第 3 個結點 65 ，由于 65 比左右孩子結點都大，則選擇一個最小的同 65 進行交換，交換後的結果為：
然後篩選第 2 個結點，由于其符合要求，是以不用篩選；最後篩選根結點 49 ，同 13 進行交換，交換後的結果為：
交換後，發現破壞了其右子樹堆的結構，是以還需要調整，最終調整後的結果為：
堆排序的實作
在實作中用到了"數組實作的二叉堆的性質"。在第一個元素的索引為 0 的情形中：
- 性質一：索引為 i 的左孩子的索引是 (2*i+1)；
- 性質二：索引為 i 的右孩子的索引是 (2*i+2)；
- 性質三：索引為 i 的父結點的索引是 floor((i-1)/2)；
是以利用最大堆進行排序的整個過程為：
- 初始化堆：将數列a[0…n]構造成最大堆；
- 交換資料：将a[0]和a[n]交換，使a[n]是a[0…n]中的最大值；然後将a[0…n-1]重新調整為最大堆。接着，将a[1]和a[n-1]交換，使a[n-1]是a[0…n-1]中的最大值；然後将a[0…n-2]重新調整為最大值。依次類推，直到整個數列都是有序的。
public class HeapSort {
public static void main(String[] args) {
int[] array = {5, 9, 1, 9, 5, 3, 7, 6, 1};// 待排序數組
sort(array);
print(array);
}
/**
* 從小到大排序
*/
public static void sort(int array[]) {
int n = array.length - 1;
// 從(n/2) --> 0逐次周遊。周遊之後，得到的數組實際上是一個(最大)二叉堆。
for (int i = n / 2; i >= 0; i--) {
heapAdjust(array, i, n);
}
// 從最後一個元素開始對序列進行調整，不斷的縮小調整的範圍直到第一個元素
for (int i = n; i > 0; i--) {
// 交換array[0]和array[i]。交換後，array[i]是array[0...i]中最大的。
swap(array, 0, i);
// 調整array[0...i-1]，使得array[0...i-1]仍然是一個最大堆。
// 即，保證array[0]是array[0...i-1]中的最大值。
heapAdjust(array, 0, i - 1);
}
}
/**
* 最大堆的向下調整算法。
* 注：數組實作的堆中，第N個節點的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。
* 其中，N為數組下标索引值，如數組中第1個數對應的N為0。
*
* @param array 待排序的數組
* @param s 被下調節點的起始位置(一般為0，表示從第1個開始)
* @param n 截至範圍(一般為數組中最後一個元素的索引)
*/
public static void heapAdjust(int array[], int s, int n) {
// 下面循環中每輪循環的父節點值或者了解為下輪循環的父節點值
int temp = array[s];
for (int i = 2 * s + 1; i <= n; i *= 2 + 1) {
// i 是左孩子，i+1 是右孩子
if (i < n && array[i] < array[i + 1]) {
i++; // 左右兩孩子中選擇較大者，即array[i + 1]
}
if (temp >= array[i]) {
break; // 父節點值最大，調整結束
}
// 将父節點和相應的左右孩子節點中最大的值給父節點
array[s] = array[i];
// 下輪循環的父節點索引
s = i;
}
array[s] = temp; // 最後将temp值賦給array[s]
}
/** 交換數組中兩個元素的位置 */
public static void swap(int array[], int low, int high) {
int temp = array[low];
array[low] = array[high];
array[high] = temp;
}
/** 列印數組 */
public static void print(int array[]) {
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
System.out.println();
}
}
堆排序的特點及性能
提示：代碼中為了展現建構堆和輸出堆頂元素後重建堆的過程，堆在建構過程中，采用的是堆的第二種關系，即父親結點的值比孩子結點的值大；重建堆的過程也是如此。
堆排序在最壞的情況下，其時間複雜度仍為O(nlogn)。這是相對于快速排序的優點所在。同時堆排序隻需要一個用于記錄交換（temp）的輔助存儲空間，所需的運作空間很小。
堆排序是不穩定的算法
，它不滿足穩定算法的定義。它在交換資料的時候，是比較父結點和子節點之間的資料，是以，即便是存在兩個數值相等的兄弟節點，它們的相對順序在排序也可能發生變化。
算法穩定性 – 假設在數列中存在a[i]=a[j]，若在排序之前，a[i]在a[j]前面；并且排序之後，a[i]仍然在a[j]前面。則這個排序算法是穩定的！