跳轉到

第二部分：優先處理

< 上一題：封包排隊 | 返回目錄 | 下一題：流量紀錄索引 >

場景：不是所有封包都平等

你的路由器同時處理各種流量：

流量類型 延遲容忍度 優先權
VoIP 語音 < 150ms 最高
視訊串流 < 300ms 高
網頁瀏覽 < 2s 中
檔案下載 不限 低

如果用普通 Queue，VoIP 封包可能被大量下載封包堵住，導致通話斷斷續續。

你需要一個**優先權佇列（Priority Queue）**：每次取出**優先權最高**的封包。

「FIFO 不夠用了。我要能快速找到『最重要』的那個。」

第 3 題：QoS 優先權管理 - Heap 與 Priority Queue

Priority Queue 是「介面」，Heap 是最常見的「實作」。這道題帶你從需求出發，理解為什麼 Heap 是最佳選擇。

(a) Priority Queue 需要什麼操作？

3 分 ・ 大二

你需要知道：Priority Queue 的核心操作是什麼？用什麼資料結構實現最好？

題目：

  1. 列出 Priority Queue 的核心操作及其語義

  2. 分析以下資料結構實現 Priority Queue 的時間複雜度：

    資料結構 Insert Extract-Max Find-Max
    未排序陣列 ? ? ?
    已排序陣列 ? ? ?
    Heap ? ? ?

  3. 為什麼 Heap 是實現 Priority Queue 的最佳選擇？

提示
  • Priority Queue 最常用的操作是 insert 和 extract-max
  • 排序的代價太高
  • Heap 是「部分有序」的結構
解答

1. 核心操作：

操作 語義
insert(x, priority) 插入元素，指定優先權
extract_max() 取出並刪除優先權最高的元素
find_max() 查看（不刪除）優先權最高的元素
increase_key(x, new_priority) 提高某元素的優先權
decrease_key(x, new_priority) 降低某元素的優先權

2. 時間複雜度比較：

資料結構 Insert Extract-Max Find-Max
未排序陣列 \(O(1)\) \(O(n)\) \(O(n)\)
已排序陣列 \(O(n)\) \(O(1)\) \(O(1)\)
Heap \(O(\log n)\) \(O(\log n)\) \(O(1)\)

3. 為什麼 Heap 最佳？

  • 未排序陣列：insert 快，但 extract-max 要掃全部
  • 已排序陣列：extract-max 快，但 insert 要移動元素維持順序
  • Heap：兩者都是 \(O(\log n)\)，取得平衡

如果你需要頻繁 insert 和 extract-max（這正是 Priority Queue 的使用場景），Heap 是最佳選擇。

數學小結：Heap 的定義

Heap 性質（以 Max-Heap 為例）：

  1. 結構性質：Complete Binary Tree（完全二元樹）
  2. 除了最後一層，每層都填滿

  3. 最後一層從左到右填

  4. 堆序性質：每個節點 ≥ 它的所有子節點

  5. 根節點是最大值

陣列實現：

對於位置 i 的節點（從 0 開始）：
- 父節點：(i-1) // 2
- 左子節點：2i + 1
- 右子節點：2i + 2

不需要指標，用陣列直接存！

(b) Heap 操作：Insert 與 Extract-Max

3 分 ・ 大二

你需要知道：Heap 如何維持「堆序性質」？

題目：

  1. 說明 insert 操作的步驟（Sift-Up / Bubble-Up）

  2. 說明 extract_max 操作的步驟（Sift-Down / Heapify）

  3. 手動模擬：對空 Max-Heap 依序 insert [3, 1, 4, 1, 5, 9, 2, 6]，畫出最終的 Heap

提示
  • Insert：先放到最後，再「上浮」到正確位置
  • Extract-Max：取出根，把最後一個放到根，再「下沉」
解答

1. Insert（Sift-Up）：

def insert(heap, x):
    heap.append(x)          # 放到最後
    i = len(heap) - 1
    while i > 0:
        parent = (i - 1) // 2
        if heap[i] > heap[parent]:
            heap[i], heap[parent] = heap[parent], heap[i]
            i = parent
        else:
            break

步驟： 1. 把新元素放到陣列末尾（維持 complete tree） 2. 和父節點比較，如果比父節點大，交換 3. 重複直到不需要交換或到達根

時間複雜度：\(O(\log n)\)（最多上浮 \(\log n\) 層）

2. Extract-Max（Sift-Down）：

def extract_max(heap):
    if not heap:
        return None
    max_val = heap[0]
    heap[0] = heap.pop()    # 把最後一個放到根
    i = 0
    while True:
        left = 2 * i + 1
        right = 2 * i + 2
        largest = i

        if left < len(heap) and heap[left] > heap[largest]:
            largest = left
        if right < len(heap) and heap[right] > heap[largest]:
            largest = right

        if largest != i:
            heap[i], heap[largest] = heap[largest], heap[i]
            i = largest
        else:
            break
    return max_val

步驟： 1. 記錄根節點（最大值） 2. 把最後一個元素移到根 3. 和較大的子節點比較，如果比子節點小，交換 4. 重複直到不需要交換或到達葉節點

時間複雜度：\(O(\log n)\)

3. 模擬建立 Heap：

依序 insert [3, 1, 4, 1, 5, 9, 2, 6]：

Insert 3:       [3]

Insert 1:       [3, 1]

Insert 4:       [4, 1, 3]    (4 > 3，上浮)

Insert 1:       [4, 1, 3, 1]

Insert 5:       [5, 4, 3, 1, 1]    (5 > 1 > 4，上浮兩次)

Insert 9:       [9, 4, 5, 1, 1, 3]  (9 > 5 > root，上浮)

Insert 2:       [9, 4, 5, 1, 1, 3, 2]

Insert 6:       [9, 6, 5, 4, 1, 3, 2, 1]  (6 > 1 > 4，上浮)

最終 Heap（樹形表示）：

        9
      /   \
     6     5
    / \   / \
   4   1 3   2
  /
 1

© Build-Heap：\(O(n)\) 建堆

4 分 ・ 大三

如果有 \(n\) 個元素要建成 Heap，一個個 insert 需要 \(O(n \log n)\)。但有更快的方法！

你需要知道：如何在 \(O(n)\) 時間內建立 Heap？

題目：

  1. 說明 Build-Heap 演算法的步驟

  2. 證明 Build-Heap 的時間複雜度是 \(O(n)\)，不是 \(O(n \log n)\)

提示
  • 從最後一個非葉節點開始，對每個節點執行 Sift-Down
  • 大部分節點在底層，Sift-Down 的距離很短
解答

1. Build-Heap 演算法：

def build_heap(arr):
    n = len(arr)
    # 從最後一個非葉節點開始，往前做 sift_down
    for i in range(n // 2 - 1, -1, -1):
        sift_down(arr, i, n)

步驟： 1. 把陣列視為 Complete Binary Tree 2. 葉節點天生滿足堆序（沒有子節點） 3. 從最後一個非葉節點開始，對每個節點執行 Sift-Down 4. 由下往上處理，確保每次 Sift-Down 時，子樹已經是合法 Heap

2. 時間複雜度證明：

直覺上，每個節點 Sift-Down 是 \(O(\log n)\)，共 \(n\) 個節點，應該是 \(O(n \log n)\)？

錯！ 大部分節點根本不需要下沉很多層。

設樹高為 \(h = \lfloor \log n \rfloor\)。

層數（從底部數） 節點數 最大下沉距離
0（葉節點） \(\approx n/2\) 0（不處理）
1 \(\approx n/4\) 1
2 \(\approx n/8\) 2
... ... ...
\(h\) 1 \(h\)

總工作量：

\[\sum_{i=1}^{h} \frac{n}{2^{i+1}} \cdot i = \frac{n}{4} \cdot 1 + \frac{n}{8} \cdot 2 + \frac{n}{16} \cdot 3 + ...\]
\[= \frac{n}{4} \sum_{i=1}^{h} \frac{i}{2^{i-1}}\]

這個級數收斂到常數（約 2），所以：

\[\text{總工作量} = O(n)\]

直覺理解：大部分節點在底層，它們下沉的距離很短（或根本不動）。只有少數節點在頂層需要下沉很長距離。「多數做少量工作 + 少數做大量工作」= 線性時間。

為什麼不用 Sift-Up？

如果從上往下，用 Sift-Up 處理每個節點：

層數（從頂部數） 節點數 最大上浮距離
0（根） 1 0
1 2 1
... ... ...
\(h\)（葉節點） \(\approx n/2\) \(h\)

總工作量 \(= \sum_{i=1}^{h} \frac{n}{2^{h-i+1}} \cdot i = O(n \log n)\)

大部分節點在底層，上浮距離長，所以慢！

(d) Heap Sort

3 分 ・ 大二

有了 Heap，排序就很簡單：反覆 extract-max，得到的就是從大到小的順序。

你需要知道：如何用 Heap 實現 in-place 排序？

題目：

  1. 說明 Heap Sort 的步驟

  2. 分析時間複雜度和空間複雜度

  3. Heap Sort 是**穩定排序**嗎？為什麼？

解答

1. Heap Sort 步驟：

def heap_sort(arr):
    n = len(arr)

    # Phase 1: Build Max-Heap
    build_heap(arr)  # O(n)

    # Phase 2: 反覆 extract-max
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]  # 最大值放到最後
        sift_down(arr, 0, i)             # 對剩餘部分做 heapify

過程： 1. 建立 Max-Heap 2. 把根（最大值）和最後一個交換，heap size - 1 3. 對新的根做 Sift-Down 4. 重複直到 heap size = 1

2. 複雜度：

  • 時間：Build-Heap \(O(n)\) + \(n\) 次 extract-max \(O(n \log n)\) = \(O(n \log n)\)
  • 空間：\(O(1)\)（in-place）

3. 穩定性：

不穩定。

例如：[5a, 5b, 3]（兩個 5）

建 Heap 後可能是 [5a, 5b, 3] 或 [5b, 5a, 3]，取決於實作細節。

Extract 過程中，相等元素的相對順序無法保證。

Heap Sort vs 其他 \(O(n \log n)\) 排序
排序 最壞時間 空間 穩定 特點
Heap Sort \(O(n \log n)\) \(O(1)\) 否 保證最壞情況，in-place
Merge Sort \(O(n \log n)\) \(O(n)\) 是 穩定，但需要額外空間
Quick Sort \(O(n^2)\) \(O(\log n)\) 否 平均最快，但最壞情況差

Heap Sort 的優勢：保證 \(O(n \log n)\) + in-place，適合記憶體受限環境。

(e) 找第 \(k\) 大元素

4 分 ・ 大三

你要找出過去一小時內，流量最大的 top 10 連線。不想排序全部資料（太慢），只想要前 \(k\) 個。

你需要知道：如何有效率地找第 \(k\) 大元素？

題目：

  1. 說明如何用 Min-Heap 維護 Top-K（而不是 Max-Heap）

  2. 分析時間複雜度

  3. Online 場景：資料持續湧入，如何即時維護 Top-K？

提示
  • 如果用 Max-Heap 存所有元素，extract-max \(k\) 次 = \(O(k \log n)\)
  • 用 Min-Heap 存「目前看到的 Top-K」，有更好的方法
解答

1. Min-Heap 維護 Top-K：

import heapq

def top_k(stream, k):
    min_heap = []

    for x in stream:
        if len(min_heap) < k:
            heapq.heappush(min_heap, x)
        elif x > min_heap[0]:
            heapq.heapreplace(min_heap, x)  # pop min, push x

    return sorted(min_heap, reverse=True)

原理： - Min-Heap 存「目前看到的最大 \(k\) 個」 - 堆頂是這 \(k\) 個中**最小**的 - 新元素進來，如果比堆頂大，就替換堆頂 - 最終堆裡就是 Top-K

為什麼用 Min-Heap？

如果用 Max-Heap 存所有 \(n\) 個元素： - 空間 \(O(n)\) - 找 Top-K 要 extract-max \(k\) 次，\(O(k \log n)\)

用 Min-Heap： - 空間 \(O(k)\) - 處理每個元素 \(O(\log k)\)

2. 時間複雜度：

  • 一次性處理 \(n\) 個元素：\(O(n \log k)\)
  • 空間：\(O(k)\)

當 \(k \ll n\) 時，遠優於排序的 \(O(n \log n)\)。

3. Online 場景：

class TopKTracker:
    def __init__(self, k):
        self.k = k
        self.min_heap = []

    def add(self, x):
        if len(self.min_heap) < self.k:
            heapq.heappush(self.min_heap, x)
        elif x > self.min_heap[0]:
            heapq.heapreplace(self.min_heap, x)

    def get_top_k(self):
        return sorted(self.min_heap, reverse=True)

每次 add 是 \(O(\log k)\)，可以處理無限流的資料。

找 Median（中位數）

更進階：即時追蹤 median（第 \(n/2\) 大）

用**兩個 Heap**： - Max-Heap 存較小的一半 - Min-Heap 存較大的一半

class MedianFinder:
    def __init__(self):
        self.lo = []  # max-heap（用負數模擬）
        self.hi = []  # min-heap

    def add(self, num):
        heapq.heappush(self.lo, -num)
        heapq.heappush(self.hi, -heapq.heappop(self.lo))
        if len(self.hi) > len(self.lo):
            heapq.heappush(self.lo, -heapq.heappop(self.hi))

    def get_median(self):
        if len(self.lo) > len(self.hi):
            return -self.lo[0]
        return (-self.lo[0] + self.hi[0]) / 2

每次 add 是 \(O(\log n)\)，get_median 是 \(O(1)\)。

進階挑戰：D-ary Heap 與 Decrease-Key

3 分 ・ 碩一

標準 Binary Heap（2-ary）每個節點有 2 個子節點。如果每個節點有 \(d\) 個子節點呢？

你需要知道：D-ary Heap 何時比 Binary Heap 更好？

題目：

  1. 分析 D-ary Heap 的各操作時間複雜度（用 \(d\) 和 \(n\) 表示）

  2. 在什麼情況下，D-ary Heap 比 Binary Heap 更適合？

  3. 說明 Decrease-Key 操作的實現與用途（提示：Dijkstra 演算法）

解答

1. D-ary Heap 複雜度：

設樹高 \(h = \log_d n = \frac{\log n}{\log d}\)

操作 Binary Heap D-ary Heap 原因
Insert \(O(\log n)\) \(O(\log_d n)\) 上浮 \(h\) 層，每層 \(O(1)\)
Extract-Max \(O(\log n)\) \(O(d \log_d n)\) 下沉 \(h\) 層，每層比較 \(d\) 個子節點
Find-Max \(O(1)\) \(O(1)\) 直接看根
Decrease-Key \(O(\log n)\) \(O(\log_d n)\) 上浮 \(h\) 層

2. 何時用 D-ary Heap？

  • Decrease-Key 頻繁：\(d > 2\) 時，上浮更快（樹更矮）
  • Extract 相對少：Extract 變慢（每層比較更多），但如果 Decrease-Key 比 Extract 多，整體更快

經典應用：Dijkstra 演算法

Dijkstra 需要 \(O(V)\) 次 Extract-Min 和 \(O(E)\) 次 Decrease-Key。

  • Binary Heap：\(O((V + E) \log V)\)
  • D-ary Heap（\(d = E/V\)）：\(O(E \log_{E/V} V)\)

當圖很密集（\(E \gg V\)）時，D-ary Heap 更快。

3. Decrease-Key 實現：

def decrease_key(heap, pos, index, new_priority):
    # pos[x] 記錄元素 x 在 heap 中的位置
    heap[index] = new_priority
    sift_up(heap, index)
    # 更新 pos mapping

用途： - Dijkstra：更新某頂點的最短距離估計 - Prim：更新某頂點到 MST 的最小邊權

需要額外維護「元素 → heap index」的 mapping。

第 3 題小結：你的優先權工具箱

「不是所有封包都平等」
    │
    ├─► (a) 快速找最大？→ Priority Queue
    │       → 用 Heap 實現
    │       → Insert/Extract-Max 都是 O(log n)
    │
    ├─► (b) Heap 怎麼運作？
    │       → Insert: Sift-Up（上浮）
    │       → Extract-Max: Sift-Down（下沉）
    │
    ├─► (c) 大量元素建堆？→ Build-Heap
    │       → 從底部 Sift-Down
    │       → O(n)，不是 O(n log n)！
    │
    ├─► (d) 順便排序？→ Heap Sort
    │       → O(n log n)，in-place，不穩定
    │
    ├─► (e) 只要 Top-K？→ Min-Heap
    │       → 空間 O(k)，時間 O(n log k)
    │
    └─► 進階：特殊需求？→ D-ary Heap
            → Decrease-Key 更快
            → Dijkstra、Prim 的好夥伴
概念 重點
Heap 性質 Complete Binary Tree + 堆序
Insert Sift-Up，\(O(\log n)\)
Extract-Max Sift-Down，\(O(\log n)\)
Build-Heap 由下往上 Sift-Down，\(O(n)\)
Top-K 用 Min-Heap，\(O(n \log k)\)
Heap Sort \(O(n \log n)\)，in-place，不穩定

< 上一題：封包排隊 | 返回目錄 | 下一題：流量紀錄索引 >