二元堆積教學：優先佇列、程式碼與時間複雜度

堆積解決什麼問題

許多程式需要從不斷變動的集合中反覆取出最緊急的項目：模擬中的下一個事件、Dijkstra 演算法中最近的未拜訪節點、優先權最高的工作，或資料流中最大的 k 個值。每次插入後都重新排序整個集合，每次要花 O(n log n)。排序串列讓移除很便宜，但插入是 O(n)。堆積讓插入與移除最小值都是 O(log n)，這正是優先佇列所需要的。

概念：存放在陣列中的樹

堆積是完全二元樹：除了最後一層之外，每一層都是滿的，而最後一層由左邊開始填入。這種形狀讓我們可以不用指標，直接把樹存在一個普通的串列中。

兩種修復操作維持堆積性質。上浮（sift up）：在尾端附加新項目後，只要它比父節點小就與父節點交換。下沉（sift down）：把最後一個項目移到根節點後，只要它比較小的子節點大，就與該子節點交換。每個操作都沿著從根到葉的一條路徑移動，所以最多約進行 log2(n) 次交換。

實例演練：push 與 pop

從最小堆積 [2, 5, 3, 9, 6] 開始（2 是根節點，它的子節點是 5 和 3，而 5 的子節點是 9 和 6）。

1. Push 1：附加在尾端，得到 [2, 5, 3, 9, 6, 1]。索引 5 的父節點是索引 2（值為 3）。
2. 1 小於 3，交換：[2, 5, 1, 9, 6, 3]。現在索引 2 的父節點是索引 0（值為 2）。
3. 1 小於 2，交換：[1, 5, 2, 9, 6, 3]。它已到達根節點，停止。
4. Pop：移除根節點 1，把最後一個項目 3 移到根節點：[3, 5, 2, 9, 6]。
5. 根節點的子節點是 5 和 2，較小的是 2，而 3 比它大，交換：[2, 5, 3, 9, 6]。索引 2 沒有子節點，停止。這次 pop 回傳了 1。

以 Python 實作最小堆積

這個類別用來展示運作機制。實際的程式碼請使用下一節介紹的 heapq。

class MinHeap:
    def __init__(self):
        self.a = []
    def push(self, x):
        a = self.a
        a.append(x)
        i = len(a) - 1
        while i > 0 and a[i] < a[(i - 1) // 2]:      # sift up
            p = (i - 1) // 2
            a[i], a[p] = a[p], a[i]
            i = p
    def pop(self):
        a = self.a
        top, last = a[0], a.pop()                   # IndexError if empty
        if a:
            a[0], i = last, 0
            while True:                             # sift down
                c = 2 * i + 1
                if c + 1 < len(a) and a[c + 1] < a[c]:
                    c += 1                          # pick the smaller child
                if c >= len(a) or a[i] <= a[c]:
                    break
                a[i], a[c] = a[c], a[i]
                i = c
        return top
h = MinHeap()
for x in [5, 3, 9, 1, 6, 2]:
    h.push(x)
print([h.pop() for _ in range(6)])  # [1, 2, 3, 5, 6, 9]

使用 Python heapq 的優先佇列

heapq 模組直接操作一般的串列，並讓它始終維持最小堆積。heapify 能在 O(n) 內就地把現有串列轉成堆積。要使用優先權，請 push 元組：Python 會逐個元素比較元組，所以第一個元素就是優先權。再加上一個計數器作為平手時的決勝條件，這樣優先權相同的項目就不需要直接互相比較。

import heapq
from itertools import count
nums = [7, 2, 9, 4, 1]
heapq.heapify(nums)
print(nums[0], heapq.heappop(nums))      # 1 1
print(heapq.nlargest(2, [7, 2, 9, 4]))   # [9, 7]
tasks, order = [], count()
heapq.heappush(tasks, (2, next(order), "write report"))
heapq.heappush(tasks, (1, next(order), "fix outage"))
heapq.heappush(tasks, (2, next(order), "reply to email"))
while tasks:
    priority, _, name = heapq.heappop(tasks)
    print(priority, name)
# 1 fix outage
# 2 write report
# 2 reply to email

對於最大堆積，Python 3.14 新增了 heapq.heapify_max、heapq.heappush_max 和 heapq.heappop_max。在較舊的版本中，常用的技巧是 push 取負值的鍵，例如 heapq.heappush(h, -score)，pop 時再取一次負值。

時間與空間複雜度

用 push 呼叫 n 次來建立堆積，成本是 O(n log n)。heapify 從最後一個父節點到根節點依序下沉，成本是 O(n)，所以當你已經擁有全部項目時，應優先使用它。

變體與常見錯誤

• 最大堆積：程式碼相同，只是比較方向反過來；在 Python 中，請使用 _max 系列函式（3.14 及之後），或把鍵取負值。
• d 元堆積：每個節點有 d 個子節點。樹較淺，使 push 更便宜，pop 則稍微貴一點。
• 索引式優先佇列 / decrease-key：heapq 無法就地修改項目的優先權。常見的替代做法（Dijkstra 演算法中使用）是 push 一筆新項目，並在舊項目被 pop 時略過它。
• 比較無法比較的項目：push (priority, dict) 時，如果兩個優先權相等，Python 會去比較 dict，進而拋出 TypeError。請把計數器放在元組的第二個位置。
• 把堆積串列當成已排序。只有 heap[0] 有保證；如果需要全部依序排列，請使用 sorted(heap)。
• 差一錯誤（off-by-one）：把教科書上從 1 開始的公式（子節點為 2i 和 2i + 1）和從 0 開始的 Python 串列混用。

何時使用堆積，以及典型問題

當你需要反覆從不斷變動的集合中，只取出最小或最大的項目時，請使用堆積。如果還需要有序迭代或任意刪除，請用排序串列或平衡樹；如果只需要一次最小值，直接用 min() 即可。

經典用途：Dijkstra 最短路徑與 Prim 最小生成樹、合併 k 個排序串列（heapq.merge）、找出最大或最小的 k 個項目（維持大小為 k 的堆積，O(n log k)）、動態中位數（兩個堆積）、工作排程器與事件驅動模擬，以及堆積排序。