基本思想
堆的定義n個關鍵字序列kl，k2，…，kn稱為堆，當且僅當該序列滿足如下性質之一（簡稱堆性質）：
ki≤k2i且ki≤k2i+1 或ki≥k2i且ki≥k2i+1（1≤i≤FLOOR(n/2)）若將此序列所存儲的向量R[1..n]看做是一棵完全二叉樹的存儲結構，則堆實質上是滿足如下性質的完全二叉樹：樹中任一非葉結點的關鍵字均不大于（或不小于）其左右孩子（若 存在）結點的關鍵字。
小根堆：根結點（亦稱為堆頂）的關鍵字是堆里所有結點關鍵字中最小的。大根堆：根結點（亦稱為堆頂）的關鍵字是堆里所有結點關鍵字中最大的。我們可以選擇大根堆或者小根堆中的任意一個來進行排序。
排序思想用大根堆排序的基本思想：
先將初始文件R[1..n]建成一個大根堆，此堆為初始的無序區。再將關鍵字最大的記錄R[1]（即堆頂）和無序區的最后一個記錄R[n]交換，由此得 到新的無序區R[1..n-1]和有序區R[n]，且滿足R[1..n-1].keys≤R[n].key。由于交換后新的根R[1]可能違反堆性質，故應將當前無序區R[1..n-1]調整為堆。 然后再次將R[1..n-1]中關鍵字最大的記錄R[1]和該區間的最后一個記錄R[n-1]交換，由 此得到新的無序區R[1..n-2]和有序區R[n-1..n]，且仍滿足關系 R[1..n-2].keys≤R[n-1..n].keys，同樣要將R[1..n-2]調整為堆。算法實現
堆排序算法，java實現，代碼如下所示：
public abstract class Sorter { public abstract void sort(int[] array); } public class HeapSorter extends Sorter { public void sort(int[] array) { heapSort(array); } /** * <p>堆排序方法 * <p>基于大根堆的堆排序方法 */ PRivate void heapSort(int[] array) { Integer tmp; // 用于交換的暫存單元 buildHeap(array); // 執行初始建堆，并調整 for (int i = 0; i < array.length; i++) { // 交換堆頂元素array[0]和堆中最后一個元素array[array.length-1-i] tmp = array[0]; array[0] = array[array.length - 1 - i]; array[array.length - 1 - i] = tmp; // 每次交換堆頂元素和堆中最后一個元素之后，都要對堆進行調整 adjustHeap(array, 0, array.length - 1 - i); } } /** * 建堆方法 * 調整堆中0~array.length/2個結點，保持堆的性質 * */ private void buildHeap(int[] array) { // 求出當前堆中最后一個存在孩子結點的索引 int pos = (array.length - 1) / 2; // 從該結點結點開始，執行建堆操作 for (int i = pos; i >= 0; i--) { adjustHeap(array, i, array.length); // 在建堆過程中，及時調整堆中索引為i的結點 } } /** * <p> * 調整堆的方法 * * @param s 待調整結點的索引 * @param m 待調整堆的結點的數量(亦即：排除葉子結點) */ private void adjustHeap(int[] array, int s, int m) { Integer tmp = array[s]; // 當前待調整的結點 int i = 2 * s + 1; // 當前待調整結點的左孩子結點的索引(i+1為當前調整結點的右孩子結點的索引) while (i < m) { if (i + 1 < m && array[i] < array[i + 1]) { // 如果右孩子大于左孩子(找到比當前待調整結點大的孩子結點) i = i + 1; } if (array[s] < array[i]) { array[s] = array[i]; // 孩子結點大于當前待調整結點，將孩子結點放到當前待調整結點的位置上 s = i; // 重新設置待調整的下一個結點的索引 i = 2 * s + 1; } else { // 如果當前待調整結點大于它的左右孩子，則不需要調整，直接退出 break; } array[s] = tmp; // 當前待調整的結點放到比其大的孩子結點位置上 } } }排序過程
假設待排序數組為array = {94,12,34,76,26,9,0,37,55,76,37,5,68,83,90,37,12,65,76,49}，數組大小為20。
第一步：初始建堆首先執行的初始建堆（在建堆的過程中需要調整堆）。過程如下：
求出當前堆中最后一個存在孩子結點的索引這里，把數組array看做是一棵完全二叉樹，這樣數組每個索引位置上的元素都對應到二叉樹中的結點，如圖所示：
其中需要在這棵樹中找到最后一個有孩子最大的一個結點的索引：pos = (array.length-1)/2 = (20-1)/2 = 9也就是索引為9的array[9] = 76，由后至前層次遍歷，從array[9]一直到array[0]，對初始堆進行調整。
先比較array[9] = 76的左右孩子：s = 9，i = 2*s+1 = 2*9 + 1 = 19，而i+1 = 19 + 1 = 20 > m = array.length-1 = 20 -1 = 19(array[9] = 76沒有右孩子)，只需要將array[9] = 76與array[i] = array[19] = 49比較，因為array[9] = 76>array[i] = array[19] = 49，則不需要交換array[9] = 76與array[i] = array[19] = 49，繼續對下一個結點（也就是array[8] = 55）進行調整；
調整結點array[8] = 55：先比較array[8] = 55的左右孩子：s = 8，i = 2*s+1 = 2*8 + 1 = 17,，而i+1 = 17 + 1 = 18 < m = array.length-1 = 20-1 = 19(array[8] = 55存在右孩子)，左孩子array[i] = array[17] = 65小于右孩子array[i+1] = array[18] = 76，只需要將array[8] = 76與右孩子array[i+1] = array[18] = 76比較，因為array[8] = 55<array[i+1] = array[18] = 76，則需要交換array[8] = 55與array[i+1] = array[18] = 76，交換后如圖所示：
繼續對下一個結點（也就是array[8] = 55）進行調整；
顯然，不需要交換；
調整結點array[6] = 0：調整結果如圖所示：
調整結果如圖所示：
調整結果如圖所示：
顯然，不需要交換。
調整結點array[2] = 34：調整結果如圖所示：
調整結果如圖所示：
顯然，不需要交換。
至此，對初始堆的調整完成。
第二步：第一次交換將堆頂元素與最后一個元素交換，即array[0] = 94與最后一個元素array[19] = 49交換，如圖所示：
此時，數組為：array = {49,76,90,12,76,68,34,37,76,26,37,5,9,83,0,37,12,65,55,94}數組中最大的元素被交換到了數組的末尾，也就是array[19] = 94是最終排好序的固定位置。
第三步：調整堆過程同前面類似。……最后經過堆排序得到有序的數組。
算法分析
時間復雜度堆排序的時間，主要由建立初始堆和反復重建堆這兩部分的時間開銷構成。堆排序的最壞時間復雜度為O(nlgn)。堆排序的平均性能較接近于最壞性能。由于建初始堆所需的比較次數較多，所以堆排序不適宜于記錄數較少的文件。
空間復雜度堆排序過程中，需要調整堆，交換待排序記錄需要一個臨時存儲單元，所以空間復雜度為O(1)。
排序穩定性堆排序是就地排序，它是不穩定的排序方法。
新聞熱點
疑難解答
