概述
堆排序是一種樹形選擇排序，是對直接選擇排序的有效改進。
堆的定義如下：具有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 個結點的完全二叉樹，則最後一個結點是第n/2個結點的子樹。
篩選從第n/2個結點為根的子樹開始（n/2是最後一個有子樹的結點），使該子樹成為堆。
之後向前依次對各結點為根的子樹進行篩選，使之成為堆，直到根結點。
如圖建堆初始過程無序序列：(49, 38, 65, 97, 76, 13, 27, 49)
(a) 無序序列，初始二叉樹，97（第8/2=4個結點）為最後一個結點（49）的父結點。
(b) 97>=49,替換位置，接下來對n/2的上一個結點65進行篩選。
(c) 13<=27且65>=13,替換65和13的位置，接下來對38進行替換（都大於它，不需操作），對49進行篩選。
(d) 13<=38且49>=13,替換49和13的位置，49>=27,替換49和27的位置。
(e) 最終得到一個堆，13是我們得到的最小數。
調整堆的方法（小頂堆）：
設有m 個元素的堆，輸出堆頂元素後，剩下m-1 個元素。將堆底元素送入堆頂，堆被破壞，其原因僅是根結點不滿足堆的性質。
將根結點與左、右子樹中較小元素的進行交換。
若與左子樹交換：如果左子樹堆被破壞，則重複方法(2).
若與右子樹交換，如果右子樹堆被破壞，則重複方法(2).
繼續對不滿足堆性質的子樹進行上述交換操作，直到葉子結點，堆被建成。
調整堆只需考慮被破壞的結點，其他的結點不需調整。
代碼實現(Java)
運行代碼結合註釋與上面的實例步驟進行對比思考。
package com.coder4j.main;public class HeapSort { /** * 調整為小頂堆（排序後結果為從大到小） * * @param array是待調整的堆數組* @param s是待調整的數組元素的位置* @param length是數組的長度* */ public static void heapAdjustS(int[] array, int s, int length) { int tmp = array[s]; int child = 2 * s + 1;// 左孩子結點的位置System.out.println("待調整結點為：array[" + s + "] = " + tmp); while (child < length) { // child + 1 是當前調整結點的右孩子// 如果有右孩子且小於左孩子，使用右孩子與結點進行比較，否則使用左孩子if (child + 1 < length && array[child] > array[child + 1]) { child++; } System.out.println("將與子孩子array[" + child + "] = " + array[child] + " 進行比較"); // 如果較小的子孩子比此結點小if (array[s] > array[child]) { System.out.println("子孩子比其小，交換位置"); array[s] = array[child];// 把較小的子孩子向上移動，替換當前待調整結點s = child;// 待調整結點移動到較小子孩子原來的位置array[child] = tmp; child = 2 * s + 1;// 繼續判斷待調整結點是否需要繼續調整if (child >= length) { System.out.println("沒有子孩子了，調整結束"); } else { System.out.println("繼續與新的子孩子進行比較"); } // continue; } else { System.out.println("子孩子均比其大，調整結束"); break;// 當前待調整結點小於它的左右孩子，不需調整，直接退出} } } /** * 調整為大頂堆（排序後結果為從小到大） * * @param array是待調整的堆數組* @param s是待調整的數組元素的位置* @param length是數組的長度* */ public static void heapAdjustB(int[] array, int s, int length) { int tmp = array[s]; int child = 2 * s + 1;// 左孩子結點的位置System.out.println("待調整結點為：array[" + s + "] = " + tmp); while (child < length) { // child + 1 是當前調整結點的右孩子// 如果有右孩子且大於左孩子，使用右孩子與結點進行比較，否則使用左孩子if (child + 1 < length && array[child] < array[child + 1]) { child++; } System.out.println("將與子孩子array[" + child + "] = " + array[child] + " 進行比較"); // 如果較大的子孩子比此結點大if (array[s] < array[child]) { System.out.println("子孩子比其大，交換位置"); array[s] = array[child];// 把較大的子孩子向上移動，替換當前待調整結點s = child;// 待調整結點移動到較大子孩子原來的位置array[child] = tmp; child = 2 * s + 1;// 繼續判斷待調整結點是否需要繼續調整if (child >= length) { System.out.println("沒有子孩子了，調整結束"); } else { System.out.println("繼續與新的子孩子進行比較"); } // continue; } else { System.out.println("子孩子均比其小，調整結束"); break;// 當前待調整結點大於它的左右孩子，不需調整，直接退出} } } /** * 堆排序算法* * @param array * @param inverse true 為倒序排列，false 為正序排列*/ public static void heapSort(int[] array, boolean inverse) { // 初始堆// 最後一個有孩子的結點位置i = (length - 1) / 2, 以此向上調整各結點使其符合堆System.out.println("初始堆開始"); for (int i = (array.length - 1) / 2; i >= 0; i--) { if (inverse) { heapAdjustS(array, i, array.length); } else { heapAdjustB(array, i, array.length); } } System.out.println("初始堆結束"); for (int i = array.length - 1; i > 0; i--) { // 交換堆頂元素H[0]和堆中最後一個元素int tmp = array[i]; array[i] = array[0]; array[0] = tmp; // 每次交換堆頂元素和堆中最後一個元素之後，都要對堆進行調整if (inverse) { heapAdjustS(array, 0, i); } else { heapAdjustB(array, 0, i); } } } public static void main(String[] args) { int[] array = { 49, 38, 65, 97, 76, 13, 27, 49 }; heapSort(array, false); for (int i : array) { System.out.print(i + " "); } }}運行結果：
初始堆開始待調整結點為：array[3] = 97將與子孩子array[7] = 49 進行比較子孩子比其小，交換位置沒有子孩子了，調整結束待調整結點為：array[2] = 65將與子孩子array[5] = 13 進行比較子孩子比其小，交換位置沒有子孩子了，調整結束待調整結點為：array[1] = 38將與子孩子array[3] = 49 進行比較子孩子均比其大，調整結束待調整結點為：array[0] = 49將與子孩子array[2] = 13 進行比較子孩子比其小，交換位置繼續與新的子孩子進行比較將與子孩子array[6] = 27 進行比較子孩子比其小，交換位置沒有子孩子了，調整結束初始堆結束待調整結點為：array[0] = 97將與子孩子array[2] = 27 進行比較子孩子比其小，交換位置繼續與新的子孩子進行比較將與子孩子array[6] = 49 進行比較子孩子比其小，交換位置沒有子孩子了，調整結束待調整結點為：array[0] = 97將與子孩子array[1] = 38 進行比較子孩子比其小，交換位置繼續與新的子孩子進行比較將與子孩子array[3] = 49 進行比較子孩子比其小，交換位置沒有子孩子了，調整結束待調整結點為：array[0] = 65將與子孩子array[1] = 49 進行比較子孩子比其小，交換位置繼續與新的子孩子進行比較將與子孩子array[4] = 76 進行比較子孩子均比其大，調整結束待調整結點為：array[0] = 76將與子孩子array[2] = 49 進行比較子孩子比其小，交換位置沒有子孩子了，調整結束待調整結點為：array[0] = 97將與子孩子array[1] = 65 進行比較子孩子比其小，交換位置沒有子孩子了，調整結束待調整結點為：array[0] = 76將與子孩子array[1] = 97 進行比較子孩子均比其大，調整結束待調整結點為：array[0] = 9797 76 65 49 49 38 27 13
PS：堆排序與直接插入排序的區別
直接選擇排序中，為了從R[1..n]中選出關鍵字最小的記錄，必須進行n-1次比較，然後在R[2..n]中選出關鍵字最小的記錄，又需要做n-2次比較。事實上，後面的n-2次比較中，有許多比較可能在前面的n-1次比較中已經做過，但由於前一趟排序時未保留這些比較結果，所以後一趟排序時又重複執行了這些比較操作。
堆排序可通過樹形結構保存部分比較結果，可減少比較次數。