第 19 章 中等 約 12 分鐘
堆積排序：用急診室來排序
把陣列建成 Heap，然後不斷取頂——出來的順序就是排序好的。O(n log n) 還省記憶體。
建議先看過： 18-heap
想法很簡單
既然 Max-Heap 的頂端永遠是最大值—— 取頂 → 放到陣列最後 → 重複 n 次 → 就排好了！
而且不用額外陣列——右邊放排好的，左邊還是 heap，原地（in-place）完成。
跑一遍：[4, 10, 3, 5, 1, 15]
Step 1：建 Max-Heap
從最後非葉節點開始 sift down。
最終 heap：[15, 10, 4, 5, 1, 3]（樹形：根 15、左 10、右 4…）
Step 2：反覆取頂
| 動作 | 陣列狀態（左 heap，右排好） |
|---|---|
| 交換 [0] 和最後一格 | [3, 10, 4, 5, 1, 15] |
| Heap size 變 5，對 [0] sift down | [10, 5, 4, 3, 1, 15] |
| 交換 [0] 和 [4] | [1, 5, 4, 3, 10, 15] |
| Sift down | [5, 3, 4, 1, 10, 15] |
| 交換 [0] 和 [3] | [1, 3, 4, 5, 10, 15] |
| Sift down | [4, 3, 1, 5, 10, 15] |
| … 繼續 … | [1, 3, 4, 5, 10, 15] |
| … | [1, 3, 4, 5, 10, 15] ✓ |
💡關鍵想法
每跑一輪：
- 把 heap 的最大值（頂端）跟「heap 的最後一個位置」交換
- 縮小 heap 範圍（最後那格已就位）
- 對新頂端 sift down
n 輪後，陣列就排好了。
Pseudocode
Algorithm HeapSort(A, n):
BuildMaxHeap(A, n) // O(n)
for i ← n-1 downto 1:
swap(A[0], A[i]) // 最大值就位
SiftDown(A, 0, i) // heap size = i
複雜度
| 情境 | Big-O |
|---|---|
| 時間（所有情況） | O(n log n) |
| 空間 | O(1) ← in-place |
| 穩定？ | 否 |
n 次取頂 × 每次 O(log n) sift down = O(n log n)。建 heap 是 O(n) 不影響整體。
跟其他 O(n log n) 排序比
| Heap Sort | Merge Sort | Quick Sort | |
|---|---|---|---|
| 平均 | O(n log n) | O(n log n) | O(n log n) |
| 最壞 | O(n log n) ✓ | O(n log n) | O(n²) ⚠️ |
| 空間 | O(1) ✓ | O(n) ⚠️ | O(log n) |
| 穩定 | 否 | 是 | 否 |
| Cache 友善 | 差（heap 跳很遠） | 中等 | 好 ✓ |
💡為什麼實務上 Quick Sort 還是比 Heap Sort 受歡迎？
Heap Sort 看起來完美——最壞 O(n log n) + O(1) 空間。
但常數倍率大：sift down 每層要比較兩個小孩、跳指標、寫回。 Quick Sort 操作對 cache 友善（連續記憶體存取），實測快 2-3 倍。
Heap Sort 的優勢場景：需要保證最壞 O(n log n) 的關鍵系統（嵌入式、即時系統）。
📝考試會這樣考
題型一：跑一遍 Heap Sort。 給陣列，列出每輪的：
- 取頂後的 heap 狀態
- 已排序的部分
訣竅：畫表格，左 heap、右排好，每輪一行。
題型二：為什麼最壞 O(n log n)？ 答：n 次取頂，每次 sift down 最多走樹高 O(log n)，所以 n × log n = O(n log n)。 最壞、平均、最好都是 O(n log n)，不像 Quick Sort 會退化。
題型三：為什麼不穩定？ 答：sift down 過程會跨越相等元素，相對順序可能變。
題型四：跟 Merge Sort 比哪個好？
- 要 in-place → Heap Sort
- 要穩定 → Merge Sort
- 要快（cache）→ Quick Sort（雖然最壞 O(n²)）
這章記住
- 建 Max-Heap → 反覆取頂並縮小範圍。
- 時間 O(n log n) 不退化、空間 O(1)。
- 不穩定，cache 不友善，所以實務 Quick Sort 還是常用。
- 考試最愛問「列出每輪 heap 狀態」——畫圖最穩。
學習進度只存在你的瀏覽器，不會上傳。