堆排序是原地排序、時間復雜度穩定 O(n log n)、無需額外空間（O(1)）的經典算法。雖然不穩定，但其最壞情況性能優於快速排序，且是理解優先隊列、Top-K 問題、外部排序的基石。本文從數據結構原理推導到 Java 代碼實現，層層遞進攻克堆排序。
| 類型 | 定義 | 典型應用 |
|---|---|---|
| 最大堆 | 父節點 ≥ 左右子節點；根節點為最大值 | 堆排序升序、優先隊列取最大 |
| 最小堆 | 父節點 ≤ 左右子節點；根節點為最小值 | Top-K 最大、優先隊列取最小 |
父節點索引： parent(i) = (i - 1) / 2
左子節點索引： left(i) = 2*i + 1
右子節點索引： right(i) = 2*i + 2
最後一個非葉子節點：lastNonLeaf = (n - 2) / 2 = n/2 - 1
這種隱式數組表示法無需指針，緊湊高效，是堆排序「原地」的關鍵。
從最後一個非葉子節點倒序到根節點，對每個節點調用 siftDown（下沉/調整），確保以該節點為根的子樹滿足堆性質。
// 自底向上構建堆：O(n)
for (int i = n/2 - 1; i >= 0; i--) {
siftDown(arr, i, n);
}
時間復雜度證明：並非 O(n log n) 而是 O(n)，因為大多數節點在樹底層，下沉高度小。具體推導見 CLRS 教材 6.3 節。
siftDown 恢復堆性質。
for (int i = n - 1; i > 0; i--) {
swap(arr, 0, i); // 最大值移至有序區
siftDown(arr, 0, i); // 在縮小的無序區重建堆
}
/**
* 將索引 k 處的元素在長度為 n 的堆中下沉到合適位置
* 前提：k 的左右子樹已是合法堆
*/
private static void siftDown(int[] arr, int k, int n) {
while (true) {
int left = 2*k + 1;
int right = left + 1;
int largest = k;
// 找出父節點與兩子節點中的最大值索引
if (left < n && arr[left] > arr[largest]) largest = left;
if (right < n && arr[right] > arr[largest]) largest = right;
// 父節點已是最大，堆性質滿足，結束
if (largest == k) break;
// 否則交換並繼續向下沉
swap(arr, k, largest);
k = largest;
}
}
private static void swap(int[] arr, int i, int j) {
int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
}
關鍵洞察：siftDown 只比較父節點與較大的子節點，每次下沉一層，最多高度 h = log₂n 次，單次調整 O(log n)。
public class HeapSort {
/** 公開入口：原地升序排序 */
public static void sort(int[] arr) {
if (arr == null || arr.length <= 1) return;
int n = arr.length;
// 1. 構建最大堆
for (int i = n/2 - 1; i >= 0; i--) {
siftDown(arr, i, n);
}
// 2. 反覆提取堆頂
for (int i = n - 1; i > 0; i--) {
swap(arr, 0, i);
siftDown(arr, 0, i);
}
}
/** 下沉調整：迭代版（避免遞歸棧溢出） */
private static void siftDown(int[] arr, int k, int n) {
while (true) {
int left = 2*k + 1;
int right = left + 1;
int largest = k;
if (left < n && arr[left] > arr[largest]) largest = left;
if (right < n && arr[right] > arr[largest]) largest = right;
if (largest == k) break;
swap(arr, k, largest);
k = largest;
}
}
private static void swap(int[] arr, int i, int j) {
int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
}
// 測試
public static void main(String[] args) {
int[] data = {4, 10, 3, 5, 1, 8, 7, 2, 9, 6};
System.out.println("排序前：" + Arrays.toString(data));
sort(data);
System.out.println("排序後：" + Arrays.toString(data));
// 輸出：[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
}
}
| 指標 | 數值 | 說明 |
|---|---|---|
| 最好時間復雜度 | O(n log n) | 無論輸入分佈，流程固定 |
| 平均時間復雜度 | O(n log n) | |
| 最壞時間復雜度 | O(n log n) | 優於快排 O(n²) 最壞情況 |
| 空間復雜度 | O(1) | 原地排序，僅常數額外空間 |
| 穩定性 | 不穩定 | 相等元素相對位置可能改變 |
| 適應性 | 無 | 不利用已有序部分 |
PriorityQueue 底層即最小堆，插入/取最小均 O(log n)。Arrays.sort() 基礎類型用雙軸快排（平均更快），對象用 TimSort（穩定、適應性強）。堆排序優勢在於最壞情況保證與原地特性。堆排序以「完全二叉樹隱式數組存儲」為基石，通過「構建堆 + 反覆提取堆頂」兩階段實現 O(n log n) 原地排序。掌握 siftDown 下沉邏輯與下標映射公式，是攻克優先隊列、Top-K、外部排序等進階話題的前提。建議手寫 2-3 遍迭代版 siftDown，體會「父節點與較大子節點比較、交換、繼續下沉」的循環不變式。
