堆的定義：滿足如下約束的 n 個關鍵字序列 K_l，K₂，…，K_n 稱為堆，1 ≤ i ≤ n/2，
   (1) k_i ≤ K_2i 且 k_i ≤ K_2i+1 （小根堆）   或

(2) K_i ≥ K_2i 且 k_i ≥ K_{2i+1 （大根堆）}

從定義來看，堆實質上是滿足如下性質的完全二叉樹：樹中任一非葉結點的關鍵字均不大于(或不小于)其左右孩子(若存在的話)結點的關鍵字。堆排序就是充分利用堆這種堆頂記錄要么是最大的要么是最小的有序性質，每次在堆中選擇最大或最小關鍵字完成排序。堆排序也是選擇排序的一種，它比直接選擇排序平均效率要高，因為直接選擇排序，每次比較之后并沒有對比較結果進行保存，導致可能存在重復的比較，而堆則利用其堆性質將比較結果保存在堆中了（非葉子節(jié)點的左邊孩子一定不大于或不小于比右邊的孩子）。

堆排序的關鍵就在于將待排序記錄的建立成堆，建好堆之后，將無序區(qū)的堆頂記錄（總是無序區(qū)的最大或最小）和無序區(qū)最后一個記錄交換，交換之后，無序區(qū)的最后一個記錄變成有序區(qū)的第一個記錄，而無序區(qū)新的的堆頂記錄不一定滿足堆性質了，因而需要將無序區(qū)調整而堆。如此循環(huán)，直到無序區(qū)為空，結束排序。

所以堆排序的主要步驟就分三步：

1，建立初始堆；

2，將無序的堆頂記錄與最后一個記錄交換，縮小無序區(qū)；

3，將交換之后的無序區(qū)調整為堆，重復步驟 2。

代碼實現：

// 篩選法調整堆，除 [low] 之外，[low] 的兩個孩子均已是大根堆 void adjust_heap(int* heap, int low, int high) { assert(heap); #if 1 // 循環(huán)實現 int i = low; int j = 2 * i; int temp = heap[i]; while (j <= high) { // 若有兩個孩子，j 為孩子中大的那個的下標 if (j < high && heap[j] < heap[j + 1]) { j = j + 1; } // 已是堆 if (temp >= heap[j]) { break; } // 繼續(xù)篩選 else { heap[i] = heap[j]; i = j; j = 2 * i; } } heap[i] = temp; #else // 遞歸實現 int i = low; int j = 2 * i; int temp = heap[i]; if (j >= high) { return; } // 若有兩個孩子，j 為孩子中大的那個的下標 if (j < high && heap[j + 1] > heap[j]) { j = j + 1; } // 已經為堆，無需調整 if (heap[low] >= heap[j]) { return; } heap[i] = heap[j]; heap[j] = temp; // 調整之后，[j, high] 可能不滿足堆了，需繼續(xù)調整 adjust_heap(heap, j, high); #endif } // 只有一個結點的樹是堆，而在完全二叉樹中，所有序號 i > n/2 的結點都是葉子， // 因此以這些結點為根的子樹均已是堆。這樣，我們只需依次將以序號為 // n/2, n/2 - 1, …, 0 的結點作為根的子樹都調整為堆即可。 void build_heap(int* heap, int length) { assert(heap && length >= 0); int i; for(i = length / 2; i >= 0; --i) { adjust_heap(heap, i, length - 1); } } // 堆排序 // void heap_sort(int* array, int length) { assert(array && length >= 0); if (length <= 1) { return; } int i, temp; // 將 [0, length - 1] 建成初始堆 build_heap(array, length); // 對當前無序區(qū) [0, i - 1] 進行堆排序，共做 length - 1 趟。 for(i = length - 1; i > 0; --i) { // 將堆頂和堆中最后一個記錄交換 temp = array[0]; array[0] = array[i]; array[i]= temp; // 將 [0, i - 1] 重新調整為堆，僅有 [0] 可能違反堆性質 adjust_heap(array, 0, i - 1); } }

時間復雜度分析：