Fibonacci Heap 標記與度數屬性詳細解析

Fibonacci Heap 節點結構

struct Node {
    Key key;
    Node* parent;
    Node* child;      // 任一子節點
    Node* left;       // 雙向循環鏈表左鄰
    Node* right;      // 右鄰
    int degree;       // 子節點數 (度數)
    bool mark;        // 是否失去過子節點
}

mark (標記) 欄位

定義

mark = true 表示該節點**自上次成為非根節點以來，已失去過一個子節點** (經歷過一次 cut 操作)。

變換規則

1. 初始建立/插入根表：mark = false。
2. Cascading Cut (級聯剪枝) 觸發：當節點 x 失去子節點 (被 cut)：
   • 若 x.mark == false：設 x.mark = true，**停止** 向上傳播。
   • 若 x.mark == true：對 x 執行 cut (從父節點斷開、加入根表)，**繼續** 對 x.parent 遞迴檢查 (級聯)。
3. 節點成為根節點 (如 extract-min 後合併)：mark = false (重置)。

目的

**限制樹高度**，確保 degree 最大為 O(log n)，進而保證摊還時間複雜度。若節點連續失去兩個子節點，直接切離升為根，避免長鏈退化。

degree (度數) 欄位

定義

節點擁有的**直接子節點數量** (非遞迴子孫總數)。

關鍵性質

對任意節點 x，其子樹大小 (含自身) 滿足：

size(x) >= F_{degree(x) + 2}   (F 為費波那契數列: F_0=0, F_1=1, F_{k+2}=F_{k+1}+F_k)

推論：degree(x) <= log_φ (size(x)) ≈ 1.44 log_2 (size(x))，即 **度數為對數級**。

Cascading Cut (級聯剪枝) 完整流程

CASCADING-CUT(H, y)
    z = y.parent
    if z != NIL
        if y.mark == FALSE
            y.mark = TRUE
        else
            CUT(H, y, z)      // 將 y 從 z 子表移除，加入 H 根表
            CASCADING-CUT(H, z) // 遞迴向上

直觀理解

• mark 就像「警告旗標」：第一次掉孩子 → 掛旗警告；第二次掉孩子 → 直接切離升職當根。
• degree 受 mark 機制間接約束，確保樹形扁平。
• 摊還分析中，mark 儲存「潛在能量」，cut 釋放能量支付實際成本。

參考資源

• 《演算法導論》第 19 章 (CLRS) - 詳細證明與摊還分析。
• MIT 6.006 課程講義 / YouTube "Fibonacci Heap" 視覺化動畫。
• CP-Algorithms: https://cp-algorithms.com/data_structures/fibonacci_heap.html

掌握 mark 與 degree 互動機制，即能理解 Fibonacci Heap 為何能達成 O(1) 插入/合併、O(log n) 刪除最小值的摊還複雜度。