本篇補上既有排序教材裡「堆積排序」只有程式、沒有資料結構本身的缺口。讀完應能獨立實作二元堆積、說明 build-heap 為什麼是線性時間，並知道 Dijkstra、Prim、Top-K 為什麼都站在優先佇列上。

相關教材：Sorting_Algorithms_Teaching_Materials.md（堆積排序的排序觀點）、Graph_Algorithms_Complete_Teaching_Materials.tex（Dijkstra、Prim）。

目錄

  1. 優先佇列在解決什麼問題
  2. 三種天真實作為什麼不夠
  3. 二元堆積的兩個不變量
  4. 陣列索引
  5. 上浮與下沉
  6. 插入與取出極值
  7. 自底向上建堆：為什麼是 O(n)
  8. 堆積排序
  9. 索引堆積與 decrease-key
  10. 複雜度總表
  11. 應用
  12. 常見陷阱
  13. C++ 實作
  14. 練習題

1. 優先佇列在解決什麼問題

普通佇列是「先進先出」。優先佇列是「優先級最高的先出」：

  • 作業系統排程：較高優先權的行程先執行。
  • 醫院分診：危急的先看，不是先到的先看。
  • 圖演算法：Dijkstra 每次要「目前已知距離最小」的頂點。

需要的操作：

操作 意思
insert(x) 放進一個元素
del-max() / del-min() 取出目前最大（或最小）並刪除
peek 只看極值，不刪
decrease-key 把已在佇列裡的某個元素的鍵變小（Dijkstra 會用到）

下面以最大堆積為例。最小堆積只是比較方向相反。

2. 三種天真實作為什麼不夠

實作 insert del-max 問題
未排序陣列 (O(1)) (O(n)) 每次取出都要掃整份
已排序陣列 (O(n)) (O(1)) 插入要挪位
平衡 BST (O(\log n)) (O(\log n)) 正確，但常數大，而且多存了「全序」這種用不到的能力

二元堆積把兩種操作都做到 (O(\log n))，而且只用一個陣列，快取友善。它不維持全序，只維持「父節點不小於子節點」。

3. 二元堆積的兩個不變量

  1. 形狀：一棵完全二元樹。最後一層從左填到右，中間不留洞。所以可以壓進陣列，不必存指標。
  2. 堆積序（heap order）：每個節點的鍵 (\ge) 它的子節點。根就是最大值。

這兩個不變量合起來，並沒有說左右子誰大。[10, 9, 8] 和 [10, 8, 9] 都是合法最大堆積。

4. 陣列索引

0-based（本篇程式用這個）：

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

1-based（很多教科書）：父 (i/2)，左 (2i)，右 (2i+1)。兩套不要混用。

例：陣列 [10, 8, 9, 4, 7, 2, 3]

        10
       /  \
      8    9
     / \  / \
    4  7 2   3

5. 上浮與下沉

只靠兩個局部修復，就能維持堆積序。

上浮 swim（插入後用）：新元素在尾巴，可能比父親大。只要比父親大就交換，一路往上，直到不大於父親或成為根。

下沉 sink（刪除根之後用）：根的位置空了，把尾巴的元素搬到根，它可能比孩子小。每次和「較大的那個孩子」交換，直到它不小於兩個孩子，或沒有孩子。

必須和較大的孩子換。若和較小的孩子換，另一個較大的孩子會違反堆積序。

手算：最大堆積 [10, 8, 9, 4, 7, 2, 3]，把根換成尾巴的 3 並刪掉尾巴，陣列暫時是 [3, 8, 9, 4, 7, 2]。

  1. 3 的孩子是 8 和 9，較大是 9，交換 → [9, 8, 3, 4, 7, 2]
  2. 3 現在沒有孩子（右子樹只到索引 2 的位置，孩子索引會超出長度）。停止。

根是 9，堆積序恢復。

6. 插入與取出極值

插入：放到陣列尾巴，然後 swim。最多沿一條根到葉的路徑，(O(\log n))。

插入 11 到上面修好的堆積：

[9, 8, 3, 4, 7, 2, 11] → 11 比父親 3 大，交換 → [9, 8, 11, 4, 7, 2, 3] → 11 比父親 9 大，交換 → [11, 8, 9, 4, 7, 2, 3]。

取出最大值：回傳根，把尾巴搬到根，長度減一，sink。同樣 (O(\log n))。

空堆積上呼叫 del-max 是錯誤，呼叫端要先檢查。

7. 自底向上建堆：為什麼是 O(n)

把任意陣列變成堆積，不要對每個元素做一次插入（那是 (O(n\log n))）。

從最後一個非葉節點往回，對每個位置做一次 sink。葉節點已經滿足堆積序，不必處理。0-based 時最後一個非葉是索引 (n/2 - 1)。

例：[4, 10, 3, 5, 1]，(n=5)，從索引 1 開始（10 的孩子是 5 和 1，已經是堆積；索引 0 的 4 才需要下沉）。

  1. 索引 1 的 10 不小於孩子，不動。
  2. 索引 0 的 4 孩子是 10 和 3，與 10 交換 → [10, 4, 3, 5, 1]。
  3. 4 的孩子是 5 和 1，與 5 交換 → [10, 5, 3, 4, 1]。

為什麼總時間是線性？ 高度為 (h) 的節點，下沉最多 (h) 步。高度 (h) 的節點個數最多約 (n / 2^{h+1})。總成本

[ \sum_{h=0}^{\lfloor \log n \rfloor} h \cdot \frac{n}{2^{h+1}} = O(n) ]

因為 (\sum h / 2^h) 收斂到常數。直覺：絕大多數節點在樹的底部，下沉距離很短；只有少數節點靠近根，才會走很長。

8. 堆積排序

  1. build-heap，(O(n))。
  2. 重複 (n-1) 次：交換根與尾巴，把尾巴視為已排序（不再屬於堆積），對新的根 sink。

每次 sink (O(\log n))，共 (O(n\log n))。額外空間 (O(1))。不穩定：相等鍵可能因為下沉交換而換位。細節與其他排序的對照見排序教材。

9. 索引堆積與 decrease-key

Dijkstra 的鬆弛是「某個頂點的距離變小了，佇列裡那一筆要更新」。一般二元堆積沒有便宜的「找到那個頂點」。

索引堆積多兩個陣列：

  • pos[v]：頂點 v 現在在堆積陣列的哪個索引。
  • inv[i]：堆積索引 i 放的是哪個頂點。

交換時兩個陣列一起改。decrease-key(v, newDist) 先改距離，再依 pos[v] 上浮。時間仍是 (O(\log n))。

若圖很稀疏、實作想省事，也可以每次鬆弛就 insert 一份新的 (dist, v)，取出時若 dist 比目前最佳還大就丟棄。正確，但堆積裡會有過期項，空間可到 (O(m))。

10. 複雜度總表

操作 二元堆積 未排序陣列 平衡 BST
insert (O(\log n)) (O(1)) (O(\log n))
del-max (O(\log n)) (O(n)) (O(\log n))
peek (O(1)) (O(n)) (O(\log n))
build (O(n)) (O(n)) (O(n\log n))
decrease-key（有索引） (O(\log n)) (O(1)) 改值後仍要 (O(n)) 找極值 (O(\log n))

(d) 元堆積把下沉的分支數變成 (d)：插入較快（樹較矮），取出較慢（要在 (d) 個孩子裡找最大）。Dijkstra 在某些圖上會用 (d>2)。

11. 應用

  • Top-K：維持大小為 (K) 的最小堆積。掃過每個數，比堆頂大才替換。時間 (O(n\log K))，空間 (O(K))。
  • 多路合併：(K) 條已排序串流，堆積放每條的當前頭。每次取出最小，推進那一條。外部排序的多路合併用這個。
  • Dijkstra / Prim：見圖論教材。沒有優先佇列時，每次線性找最小距離頂點，總時間退回 (O(n^2))。
  • 事件驅動模擬：下一個事件時間最小的先處理。
  • 霍夫曼編碼：每次合併兩個頻率最小的節點。見貪心教材。

12. 常見陷阱

  • 和較小的孩子交換。 下沉必須選較大的孩子。
  • 0-based / 1-based 公式混用。 父節點算成負索引或指到自己，迴圈不會停。
  • sink 的範圍用了舊長度。 取出極值後，尾巴已經「排序好」或不屬於堆積，下沉的右邊界要是新的堆大小。
  • 把「是最大堆積」理解成「陣列已排序」。 [10, 8, 9] 是堆積，但不是排序結果。
  • 相等鍵與穩定性。 堆積排序不穩定，不能拿來做需要保留原順序的多鍵排序。
  • 空堆、單元素。 swim / sink 在沒有父或沒有子時必須直接返回。

13. C++ 實作

#include <stdexcept>
#include <utility>
#include <vector>

class MaxHeap {
public:
    void push(int x) {
        a_.push_back(x);
        swim(static_cast<int>(a_.size()) - 1);
    }

    int top() const {
        if (a_.empty()) throw std::logic_error("empty heap");
        return a_[0];
    }

    int pop() {
        int m = top();
        a_[0] = a_.back();
        a_.pop_back();
        if (!a_.empty()) sink(0);
        return m;
    }

    bool empty() const { return a_.empty(); }

    // 把任意陣列就地變成最大堆積。
    static void build(std::vector<int>& a) {
        for (int i = static_cast<int>(a.size()) / 2 - 1; i >= 0; --i)
            sink_range(a, i, static_cast<int>(a.size()));
    }

private:
    std::vector<int> a_;

    void swim(int i) {
        while (i > 0) {
            int p = (i - 1) / 2;
            if (a_[p] >= a_[i]) break;
            std::swap(a_[p], a_[i]);
            i = p;
        }
    }

    void sink(int i) { sink_range(a_, i, static_cast<int>(a_.size())); }

    static void sink_range(std::vector<int>& a, int i, int n) {
        while (true) {
            int l = 2 * i + 1, r = l + 1, big = i;
            if (l < n && a[l] > a[big]) big = l;
            if (r < n && a[r] > a[big]) big = r;
            if (big == i) break;
            std::swap(a[i], a[big]);
            i = big;
        }
    }
};

14. 練習題

  1. 對 [1, 2, 3, 4, 5] 做自底向上建最大堆積，寫出每一步陣列。
  2. 說明為什麼逐一插入建堆是 (O(n\log n))，而自底向上是 (O(n))。兩者最後都合法，但形狀可以不同。
  3. 用大小為 3 的最小堆積，從 [7, 1, 9, 3, 8, 2] 取出最大的 3 個數。堆積裡最後應該剩哪些？
  4. 為什麼 Dijkstra 若只用「無索引的堆積 + 過期項丟棄」仍然正確？什麼時候這個做法會比索引堆積費空間？
  5. 堆積排序是原地的，為什麼仍不適合作為「需要穩定」的排序？

參考答案

  1. 從索引 1 往回。索引 1 的 2 與孩子 4、5 中較大的 5 交換，得 [1, 5, 3, 4, 2]，2 沒有孩子。索引 0 的 1 與 5、3 中的 5 交換，得 [5, 1, 3, 4, 2]；1 再與 4 交換，得 [5, 4, 3, 1, 2]。
  2. 逐一插入時，第 (i) 個元素可能上浮 (\Theta(\log i)) 層，總和是 (\sum \log i = \Theta(n\log n))。自底向上時大多數節點下沉距離是常數，級數 (\sum h/2^h) 收斂，總和線性。
  3. 掃過後最小堆積大小維持 3，堆內是目前看過的最大三個：9, 8, 7（順序依插入過程而定，集合是這三個）。
  4. 過期項的距離比該頂點已記錄的最佳距離差，彈出時忽略即可，第一次彈出某頂點時的距離就是最短距離（非負權）。同一頂點可在堆內出現多次，鬆弛次數多時空間可到 (O(m))。
  5. 下沉與建堆的交換不看「誰先出現」，相等鍵的相對順序會被打亂。穩定排序要另選合併排序或計數／基底排序。

小結

二元堆積用「完全樹的形狀 + 父大於子」換到插入與取極值都是 (O(\log n))，建堆還能做到 (O(n))。它不是排序好的陣列。需要改已存在元素的鍵時，加上索引，或接受過期項。堆積排序、Top-K、多路合併、Dijkstra 與 Prim 都是這兩個操作的直接應用。