堆積排序

🎯 什麼情境該想到我

當你「記憶體極度吃緊，又不能接受最差 $O(n^2)$」的時候。
★ 它是**唯一同時做到「原地」與「最差 $O(n\log n)$ 保證」**的經典排序——但實務上幾乎只以「introsort 的後備方案」的身分出現。

⚙️ 怎麼用（機制與推導）

兩階段

① 建最大堆（Build-Max-Heap）          O(n)    ← ★ 這裡有個漂亮的推導
② 重複：把根（最大值）換到陣列尾端，
   堆大小減一，對新的根做下濾           n × O(log n)
─────────────────────────────────────
總計                                    O(n log n)

[5 2 4 6 1 3]  ─建堆→  [6 5 4 2 1 3]
                        ↑ 最大值在根

[6 5 4 2 1 3] → 換 6 和 3 → [3 5 4 2 1 | 6]  → 下濾 → [5 3 4 2 1 | 6]
[5 3 4 2 1 | 6] → 換 5 和 1 → [1 3 4 2 | 5 6] → 下濾 → [4 3 1 2 | 5 6]
⋯
已排序的部分從右邊長出來，堆從左邊縮小 —— ★ 完全原地

func HeapSort[T cmp.Ordered](a []T) {
    n := len(a)
    // ① 建堆：★ 從最後一個「非葉節點」開始往前，葉節點本身就是合法的堆
    for i := n/2 - 1; i >= 0; i-- {
        siftDown(a, i, n)
    }
    // ② 逐一取出
    for i := n - 1; i > 0; i-- {
        a[0], a[i] = a[i], a[0]
        siftDown(a, 0, i)     // 堆的有效範圍縮小到 [0, i)
    }
}
 
func siftDown[T cmp.Ordered](a []T, root, n int) {
    for {
        child := 2*root + 1              // 左子節點
        if child >= n {
            return
        }
        if child+1 < n && a[child+1] > a[child] {
            child++                      // 取較大的子節點
        }
        if a[root] >= a[child] {
            return
        }
        a[root], a[child] = a[child], a[root]
        root = child
    }
}

★ 為什麼建堆是 $O(n)$ 而不是 $O(n\log n)$（經典追問）

天真的估計：$n/2$ 個節點各做一次 $O(\log n)$ 的下濾 → $O(n\log n)$。這是錯的（估太鬆）。

關鍵觀察：下濾的成本取決於節點的「高度」，而絕大多數節點都在底部、高度很小。

高度為 $h$ 的節點最多有 $\lceil n/2^{h+1}\rceil$ 個，每個的下濾成本是 $O(h)$：

${\sum }_{h=0}^{\lfloor \log n\rfloor }\lceil \frac{n}{2^{h+1}}\rceil O(h)=O\left(n{\sum }_{h=0}^{\infty }\frac{h}{2^h}\right)$

而 $\sum _{h=0}^{\infty }\frac{h}{2^h}=2$（等比級數微分的標準結果），所以：

$\boxed{\text{建堆}=O(2n)=O(n)}$

直覺版：一半的節點是葉子，完全不用動；只有根那一個節點要走完整的 $\log n$。
成本集中在少數高節點，總和被壓成線性。

（但整體仍是 $O(n\log n)$，因為第二階段的 $n$ 次取出各要 $O(\log n)$。）

四個性質

性質	說明
原地	✅ $O(1)$ 額外空間——唯一的賣點
最差保證	✅ $\Theta (n\log n)$，沒有壞情況
穩定	❌ 交換會打亂相等元素的順序
★ 快取友善	❌ 這是它實務上慢的原因

★ 為什麼實務上比快排慢（明明同為 $\Theta (n\log n)$）

記憶體存取模式完全不同：

快速排序：兩根指標從兩端往中間掃  →  連續存取，快取命中率高
          ────▶              ◀────

堆積排序：父 i → 子 2i+1        →  ★ 索引呈指數跳躍，深處的存取幾乎必定 cache miss
          0 → 1 → 3 → 7 → 15 → 31 → …

$n$ 很大時，a[2i+1] 和 a[i] 早就不在同一個快取行（cache line）裡了。
現代 CPU 上快取失誤的代價是算術運算的百倍，所以堆積排序的常數大得多。

★ 這是「相同漸進複雜度，實測差好幾倍」最經典的案例之一。

它真正的用途

用途	說明
★ Introsort 的後備	C++ std::sort：快排遞迴深度超過 $2\log n$ 就切換成堆積排序。 取快排的平均速度 + 堆積排序的最差保證（見 快速排序）
記憶體極度受限	嵌入式、核心程式碼
★ 優先佇列（更常見）	堆本身比堆積排序有用得多——見 二元堆積
Top-K	只要前 $k$ 大，不需要完整排序 → $O(n\log k)$（見 順序統計量與中位數）

🧪 我實際套用的紀錄

• （待填）

⚠️ 注意 / 什麼時候不適用

• ★ 不穩定。要穩定用 合併排序 家族。
• 實務上不會直接選它。Go 用 slices.Sort，需要穩定用 slices.SortStableFunc——兩者都不是堆積排序。
• 建堆的迴圈起點是 n/2 - 1，不是 n-1。從 n/2 開始的都是葉節點，本身就合法。寫錯不會報錯，只會排不對。
• siftDown 用迴圈不要用遞迴。遞迴版在 $n$ 很大時有額外的呼叫開銷（雖然是尾遞迴，Go 不保證消除）。
• Go 的 container/heap 是最小堆（官方文件：“each node is the minimum-valued node in its subtree”），要最大堆得把 Less 反過來寫。
• 別把「堆積排序」和「堆」搞混。前者實務價值低，後者（優先佇列）到處都在用。

🔗 相關工具

• 二元堆積 —— 底層資料結構；優先佇列才是它真正的價值
• 快速排序 —— introsort 中的主角，堆積排序是它的保險
• 合併排序 —— 另一個有 $\Theta (n\log n)$ 保證的選擇（但要額外空間）
• 順序統計量與中位數 —— Top-K 問題
• 演算法導論