堆排序算法深度解析：原理圖解與 Java 高性能實現

堆排序作為選擇排序的優化版本，以 O(n log n) 最壞情況時間複雜度和 O(1) 空間複雜度，成為不穩定排序中的性能標桿。本文從堆定義、建堆調整、排序流程三個維度圖解原理，並提供含詳細日誌輸出的 Java 完整實現代碼。

一、 堆的數學定義與結構特性

序列 (k1, k2, ..., kn) 稱為堆，當且僅當滿足：

• 小頂堆：ki ≤ k2i 且 ki ≤ k2i+1（根節點最小）
• 大頂堆：ki ≥ k2i 且 ki ≥ k2i+1（根節點最大）

一維數組存儲對應完全二叉樹，非葉節點索引範圍 [0, n/2 - 1]，葉節點索引 [n/2, n-1]。

二、 核心操作：建堆與調整

1. 建堆（自底向上）

從最後一個非葉節點 i = (n-1)/2 遞減至 0，依次調用 heapAdjust 使以該節點為根的子樹滿足堆性質。過程中元素下沉，最終根節點為極值。

2. 調整堆（自頂向下）

輸出堆頂後，將堆尾元素移至堆頂，從根節點開始：比較左右子節點，與極值子節點交換，繼續向下調整，直至葉節點或滿足堆性質。關鍵優勢：利用樹形結構保留比較結果，避免直接選擇排序的重複比較。

三、 算法流程圖解（以小頂堆為例）

初始序列：[49, 38, 65, 97, 76, 13, 27, 49]

1. 建堆階段：97↔49、65↔13、49↔13→27，最終堆頂 13
2. 排序階段：堆頂 13 與尾部 49 交換，調整剩餘 7 元素堆，重複直至有序

最終輸出升序序列：[13, 27, 38, 49, 49, 65, 76, 97]

四、 Java 完整實現（雙向排序支援）

public class HeapSort {
    // 小頂堆調整（輸出降序）
    public static void heapAdjustS(int[] arr, int s, int len) { ... }
    // 大頂堆調整（輸出升序）
    public static void heapAdjustB(int[] arr, int s, int len) { ... }

    public static void heapSort(int[] arr, boolean inverse) {
        // 1. 建初始堆
        for (int i = (arr.length - 1) / 2; i >= 0; i--) {
            inverse ? heapAdjustS(arr, i, arr.length) : heapAdjustB(arr, i, arr.length);
        }
        // 2. 依次輸出堆頂並調整
        for (int i = arr.length - 1; i > 0; i--) {
            swap(arr, 0, i);
            inverse ? heapAdjustS(arr, 0, i) : heapAdjustB(arr, 0, i);
        }
    }
}

代碼內置詳細 System.out.println 日誌，輸出每步調整節點、比較子節點、交換決策，運行輸出可作為算法動畫級教學參考。

五、 性能對比與應用場景

適用場景：海量數據 Top-K 問題、外部排序內存受限環境、實時系統要求確定性時間複雜度場景。Java PriorityQueue 底層即基於堆實現。

六、 總結

堆排序通過完全二叉樹隱式結構，將選擇排序的 O(n²) 比較次數優化至 O(n log n)，是原地排序算法的理論極限之一。掌握其「建堆-輸出-調整」三部曲，不僅能應對面試考察，更能深入理解數據結構如何服務於算法優化。