10.2 資料結構與演算法的互動#

概念說明#

「程式 = 資料結構 + 演算法」不僅是加法，更是互動：演算法對資料結構提出操作需求，資料結構的操作成本直接決定演算法的總複雜度；反過來，好的資料結構能讓原本遙不可及的演算法變得實用。

正向：資料結構加速演算法#

同一個演算法骨架，換資料結構就換了效率等級：

例一：Dijkstra 的兩種實現

演算法思想（貪心放鬆）完全相同，堆積把「挑最小」從 O(V) 壓到 O(log V)。

例二：兩數之和（4.3 節）——把「查詢另一半」從串列 O(n) 換成雜湊表 O(1)，整體從 O(n²) 降到 O(n)。例三：Kruskal——排序讓「貪心選邊」有理可循，併查集讓「會不會成環」從 O(V+E) 的 BFS 檢查壓到近 O(1)。

反向：演算法為資料結構服務#

有時是演算法的進步讓結構值得建：費式堆積（Fibonacci heap）把 Dijkstra 的「 decrease-key」攤攤做到 O(1)，理論複雜度降到 O(E + V log V)——雖然常數大、實務少用，卻主導了理論界的複雜度論證。又如快排選 pivot 的「中位數的中位數」演算法，本身是一場小型資料結構重組。

設計演算法時問：這個操作最貴在哪？有沒有結構能把這一步變便宜？ 這條問句是本章的心法。

實作：同一問題的三種演算法—結構搭配#

問題：不斷插入數字，隨時查「目前的中位數」。

import heapq

class MedianHeap:
    """雙堆法：max-heap 存小半、min-heap 存大半，各堆大小差 ≤ 1"""
    def __init__(self):
        self.low = []      # 最大堆積（存負數模擬）
        self.high = []     # 最小堆積

    def add(self, x):
        heapq.heappush(self.low, -x)
        # 保證 low 的最大 ≤ high 的最小
        heapq.heappush(self.high, -heapq.heappop(self.low))
        if len(self.high) > len(self.low):      # 平衡大小
            heapq.heappush(self.low, -heapq.heappop(self.high))

    def median(self):
        if not self.low:
            raise IndexError("空的")
        if len(self.low) > len(self.high):
            return -self.low[0]
        return (-self.low[0] + self.high[0]) / 2

m = MedianHeap()
for x in [5, 2, 8, 4, 7, 1, 9]:
    m.add(x)
    print(f"加入 {x} → 中位數 {m.median()}")
# 5 → 3.5 → 5 → 4.5 → 5 → 4.5 → 5

三種搭配的比較：

雙堆法是「演算法設計（把問題切兩半、維護不變式）× 現成結構（堆積）」共舞的典範：沒有一個叫「中位數堆積」的現成結構，但我們用兩個堆積拼了出來。

複雜度分析#

複雜度是「演算法骨架的操作次數 × 資料結構單次操作成本」的乘積（或組合）。分析順序：先數演算法每步做什麼操作、做幾次，再代入結構的操作成本表，最後得出總式。實測驗證時留意常數與快取效應（第2章的教訓：理論 O(n) 的鏈結串列實測可能輸給理論較差的動態陣列）。

練習#

1. 把「求中位數」擴充成「求滑動視窗中位數」：視窗滑動時需同時刪除舊元素。雙堆法的「任意刪除」是弱點，請設計惰性刪除方案。
2. 拓撲排序可以用 DFS（堆疊）或 Kahn 演算法（佇列 + 入度表）實現，兩者分別對應什麼資料結構操作模式？何者更容易輸出「第幾學期修什麼課」的分批結果？
3. 挑一個你在前幾章寫過的程式，問「最貴的操作是什麼、有沒有結構能讓它變便宜」，實際改造並量測前後差異。