二元堆積

🎯 什麼情境該想到我

當你「要反覆取出目前最小／最大的那個」的時候——排程器、計時器、Top-K、Dijkstra、合併多路有序串流。
★ 堆積排序 是它最不重要的用途；「優先佇列」才是。

⚙️ 怎麼用（機制與 Go 實作）

結構：用陣列表示的完全二元樹

完全二元樹（除最後一層外都填滿，最後一層靠左）可以用純陣列表示，不需要任何指標：

索引：    0
        /   \
       1     2
      / \   / \
     3   4 5   6

父節點 = (i-1)/2
左子   = 2i+1
右子   = 2i+2

★ 「不需要指標」是它效率的來源：連續記憶體、零配置、快取友善（相對於樹狀結構）。

堆序性質（最小堆）：每個節點 ≤ 它的兩個子節點。
→ 根一定是最小值，但兄弟之間沒有任何保證（這不是排序好的陣列）。

兩個核心操作

Push(v)：放到陣列尾端 → ★ 上濾（sift up）：和父比較，比父小就往上換
Pop()  ：取走根 → 把尾端元素搬到根 → ★ 下濾（sift down）：和較小的子交換

兩者都是沿著一條根到葉的路徑走，所以都是 $O(\log n)$。

複雜度

操作	複雜度
Peek（看最小值）	$O(1)$
Push	$O(\log n)$
Pop	$O(\log n)$
建堆（Build-Heap）	$O(n)$ ← 不是 $O(n\log n)$，推導見 堆積排序
查找任意元素	$O(n)$ ← ★ 堆不支援查找
刪除任意元素	$O(\log n)$，但要先知道它的索引

★ Go 的 container/heap

官方定義是最小堆（“each node is the minimum-valued node in its subtree”，2026-09-20 查證）。
它是一個 interface 導向的套件——你提供 Less/Swap/Push/Pop，它提供演算法。

type Item struct {
    value    string
    priority int
    index    int       // ★ 給 heap.Fix 用：讓你能 O(log n) 更新既有元素
}
 
type PQ []*Item
 
func (pq PQ) Len() int { return len(pq) }
// ★ 要最大堆就把這裡反過來寫：return pq[i].priority > pq[j].priority
func (pq PQ) Less(i, j int) bool { return pq[i].priority < pq[j].priority }
func (pq PQ) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
    pq[i].index, pq[j].index = i, j     // ★ 交換時要同步維護 index
}
func (pq *PQ) Push(x any) {
    it := x.(*Item)
    it.index = len(*pq)
    *pq = append(*pq, it)
}
func (pq *PQ) Pop() any {
    old := *pq
    n := len(old)
    it := old[n-1]
    old[n-1] = nil          // ★ 清零避免記憶體洩漏
    it.index = -1
    *pq = old[:n-1]
    return it
}
 
// 使用
pq := &PQ{}
heap.Init(pq)
heap.Push(pq, &Item{value: "task", priority: 3})
top := heap.Pop(pq).(*Item)
 
// ★ 改了某個元素的優先序之後，一定要呼叫 Fix
item.priority = 1
heap.Fix(pq, item.index)

三個容易寫錯的地方：

1. heap.Push 不是 pq.Push —— 前者會做上濾，後者只是 append。直接呼叫 pq.Push 會破壞堆序。
2. Swap 裡要維護 index，否則 heap.Fix 會改錯位置。
3. Pop 要清零指標，否則底層陣列持有已移除的元素（同 堆疊與佇列）。

★ 它的主要用途

用途	說明
優先佇列	排程器、任務佇列（按優先序而非到達順序）
★ 計時器	「最快到期的那個」正是堆頂。Go runtime 的 timer、多數事件迴圈都用堆（或其變體）
Dijkstra 最短路徑、Prim 最小生成樹	「取出目前距離最小的點」——堆讓這步從 $O(V)$ 降到 $O(\log V)$
Top-K	大小為 $k$ 的堆，$O(n\log k)$，只要 $O(k)$ 記憶體（見 順序統計量與中位數）
合併 $k$ 路有序串流	堆裡放每路的當前元素，$O(n\log k)$——外部排序的合併階段
中位數維護	兩個堆（最大堆存小的一半、最小堆存大的一半），$O(\log n)$ 插入、$O(1)$ 取中位數

和其他結構的界線

你要的	用
只要最小／最大，反覆取	堆
要完整排序	快速排序 / 合併排序
要任意鍵查找	雜湊表
要有序 + 範圍查詢 + 任意刪除	紅黑樹
要第 k 個（一次性）	順序統計量與中位數 的 quickselect

🧪 我實際套用的紀錄

• （待填）

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

• ★ 堆不支援查找。「這個元素在不在堆裡」是 $O(n)$。需要「查找 + 更新優先序」就要額外維護一個 map[key]index——這正是 Dijkstra 的標準實作方式。
• 堆不是排序好的陣列。pq[1] 和 pq[2] 之間沒有任何順序保證，直接 range 出來的順序是無意義的。
• 不穩定：相同優先序的元素取出順序不確定。需要 FIFO 語義就在鍵裡加一個遞增序號。
• container/heap 沒有泛型（回傳 any，要型別斷言）。熱路徑上可以自己寫泛型版本省掉裝箱。
• 改了優先序一定要 heap.Fix，否則堆序被破壞且不會報錯——這是最隱蔽的 bug。
• 更好的理論選擇存在但實務上沒用：Fibonacci heap 的 decrease-key 是攤還 $O(1)$（讓 Dijkstra 理論上更快），但常數極大，實測幾乎總是輸給二元堆。

🔗 相關工具

• 堆積排序 —— 同一個結構的另一個用途，以及建堆 $O(n)$ 的推導
• 順序統計量與中位數 —— Top-K 的堆做法
• Dijkstra 最短路徑、Prim 最小生成樹 —— 主要客戶
• 堆疊與佇列 —— 對照：按到達順序 vs 按優先序
• 演算法導論