堆積與優先佇列：醫院急診室

急診室不排隊

你進急診，分檢護理師看一眼——

心臟病發 → 馬上看
流感發燒 → 等
小擦傷 → 更後面

先到先服務不公平。要按「緊急程度」排。

堆積 (Heap) 就是電腦版的急診室：總是把「最重要的」放在最上面，新進來的會自動插到對的位置。

Max-Heap：最大值在頂

💡陣列下標的數學魔法

Heap 用陣列存（不用 pointer），因為它是「完全二元樹」——從左到右填滿。

節點 i 的左小孩：2i + 1
節點 i 的右小孩：2i + 2
節點 i 的父親：(i - 1) / 2

這就是為什麼 heap 比 BST 省記憶體（沒有 left/right pointer）。

兩個關鍵操作

插入：往上爬（Sift Up）

插入新值放到最後一格，然後和父親比，比父親大就跟父親換，一路換到不能換為止。

插入 60 到上面那棵 heap：

1. 60 放到 [7]（最後一格）
2. 父親是 [3]=10，60 > 10 → 換
3. 父親是 [1]=30，60 > 30 → 換
4. 父親是 [0]=50，60 > 50 → 換
5. 已經到頂，停。 ✓

新 heap：[60, 50, 40, 30, 20, 35, 15, 10]

最多走樹的高度 → O(log n)。

取最大值：往下沉（Sift Down）

最大值永遠在頂端 [0]。取出後，把最後一格搬到頂，然後和較大的小孩比，比小孩小就跟小孩換，一路換到不能換為止。

從 [50, 30, 40, 10, 20, 35, 15] 取出 50：

1. 取出 50
2. 把最後一格 15 搬到頂 → [15, 30, 40, 10, 20, 35]
3. 15 vs (30, 40) → 較大的 40 ≥ 15 → 換
   [40, 30, 15, 10, 20, 35]
4. 15 vs (35) → 35 ≥ 15 → 換
   [40, 30, 35, 10, 20, 15]
5. 無子節點，停。 ✓

最多走樹的高度 → O(log n)。

Pseudocode

Algorithm Insert(A, value):

A.append(value)

i ← len(A) - 1

while i > 0 and A[(i-1)/2] < A[i]:

swap(A[(i-1)/2], A[i])

i ← (i-1) / 2

Algorithm ExtractMax(A):

max ← A[0]

A[0] ← A[last]

A.pop()

SiftDown(A, 0)

return max

從一個陣列建 Heap（神奇的 O(n)）

從最後一個非葉節點開始，往前每個都做 sift down。

A = [3, 1, 4, 1, 5, 9, 2, 6]
從 index = (8/2 - 1) = 3 開始，往 0 走
i=3: sift down → ...
i=2: sift down → ...
i=1: sift down → ...
i=0: sift down → ...

💡為什麼建 heap 是 O(n) 不是 O(n log n)?

直覺：每個節點的 sift down 成本 = 它的高度。葉節點（n/2 個）高度 0、上一層（n/4 個）高度 1、… 總和 = n/2 × 0 + n/4 × 1 + n/8 × 2 + … = O(n)（級數收斂）

考試會問這個證明，記住「葉節點很多但很便宜」就好。

複雜度

操作	Big-O
插入 (Insert)	O(log n)
取頂 (Peek max)	O(1)
取頂並移除 (Extract max)	O(log n)
從陣列建 heap	O(n)
找最小值（在 max-heap）	O(n) ⚠️

Heap vs BST

	Heap	BST 平衡
找最大/最小	O(1)	O(log n)
找任意值	O(n)	O(log n)
排序走訪	不行（heap 不是排序的）	O(n) 中序
用途	優先佇列、排序、top-K	一般查詢、範圍查詢

📝考試會這樣考

題型一：給陣列，依序插入並畫 heap。 例：依序插入 4, 10, 3, 5, 1, 15 到空 max-heap，畫出每步。每次插入都要寫 sift up 過程。

題型二：給 heap，extract max 後畫出新狀態。 記得：取頂 → 最後一格搬到頂 → sift down。

題型三：給陣列，用 build-heap 建立 max-heap。 從 i = n/2 - 1 開始往 0 走，每個 sift down。

題型四：證明建 heap 是 O(n)。 列出每層的節點數 × 高度，求和。

題型五：父子下標公式。 A[i] 的左子是 A[2i+1]，右子 A[2i+2]，父親 A[(i-1)/2]。死背。

這章記住

Heap = 完全二元樹，用陣列存。父子下標用乘 2 / 除 2 計算。
Max-Heap 頂端永遠是最大值（Min-Heap 頂端是最小值）。
插入 O(log n)、取頂 O(log n)、建 heap O(n)。
Heap 用來實作優先佇列——Dijkstra、A*、Top-K 都靠它。