← 回首頁

費氏堆與 Link-Cut 樹（Fibonacci Heap / Link-Cut Tree）

這兩個結構在解什麼問題? 費氏堆(Fibonacci Heap)是「更快的優先佇列」——像 Dijkstra 找最短路、Prim 建最小生成樹這類演算法, 過程中要一直「把某個元素的優先度調小」(decreaseKey),費氏堆讓這個動作幾乎不花時間,整體就更快。 Link-Cut 樹(動態樹)則專門處理「一片會一直長出新邊、砍掉舊邊的樹林」,隨時要問「這兩點還連在一起嗎」,它能很快回答。
這兩者都是「攤銷分析」的經典例子——意思是:單一次操作偶爾看起來很貴,但把成本分攤到一長串操作後,平均每次其實很便宜 (就像月票單買一趟很貴,但整個月搭下來平均每趟很划算)。下面兩節分別示範費氏堆的懶惰合併/級聯剪切,以及動態樹的接邊、斷邊、換根。

1. 費氏堆（Fibonacci Heap，懶惰插入 + consolidate + 級聯剪切）

insert(key) 不做任何整理，直接把新節點掛入根鏈（環形雙向鏈結），只更新 min 指標，O(1) 攤銷。 extractMin() 取出目前 min，其子節點全數升入根鏈，而後呼叫 consolidate()：用「度數表」逐一掃描根鏈， 同度數的根兩兩合併（key 較大者掛到較小者之下、度數 +1），直到合併完成後所有根度數兩兩相異， O(log n) 攤銷。decreaseKey(oldKey, newKey) 更新鍵值後，若違反 min-heap 序（新值 < 父節點 key）， 呼叫 cut() 把該節點剪到根鏈，並對其父節點呼叫 cascadingCut()——父節點若尚未標記（marked）則標記它 （代表「已失去過一個子節點」），若已標記則父節點自己也被剪到根鏈、並遞迴向上檢查祖父節點， 這就是級聯剪切的發生點。畫面中節點上方 ＊ 標示 marked=true 的節點，min 標示目前 的 min 指標；黃框（frontier）＝ consolidate 正在合併的兩根，綠色（finalized）＝ 本次操作剛剪出 根鏈或合併完成的根。

固定腳本：insert 9 個元素（[7,3,17,24,18,52,38,45,9]，依序懶惰入根鏈）→ extractMin()（獨立驗證：Math.min(...FH_INSERTS)=3，與腳本回傳值一致；觸發 consolidate，8 個度數 0 的根疊合成單一 binomial 樹，共 7 次合併，終根 key=7 度數 3）→ decreaseKey(45→2)（key=9 首次失去 子節點 45，被標記 marked=true）→ decreaseKey(38→1)（key=9 再失去子節點 38，觸發級聯剪切：9 本身 被剪出根鏈、清除標記，遞迴檢查其父 7 時 7 為根故級聯到此為止）。

操作腳本

    已執行操作數：0 目前堆大小：0
    森林佈局每幀由堆快照重算：根鏈依序水平排列，同一根的子樹向下延伸（tidy-tree，子樹寬度互不重疊）。 橘色（current）＝ min 指標或當前處理節點；黃框（frontier）＝ consolidate 正在合併的兩根； 綠色（finalized）＝ 本次操作剛完成合併的根、或剛被剪出根鏈的節點；節點上方 ＊ ＝ marked（已失去 過一個子節點，尚未觸發級聯）、min ＝ 目前 min 指標所在的根（兩者互斥顯示，皆不出現時代表一般 非標記、非 min 的節點）。

    合併紀錄（mergeLog，consolidate 合併對）

    剪切紀錄（cutLog，含級聯剪切）

    已執行操作紀錄（opLog）

    本頁 Min-Heap 家族的基本操作（上浮/下沉）可見 → 堆積與字典樹 Heap/Trie； 費氏堆用懶惰合併＋標記機制把 decreaseKey 攤銷降為 O(1)，是二元堆做不到的優勢。

    2. Link-Cut Tree（動態樹，makeRoot/link/cut/connected/findRoot）

    Link-Cut Tree 維護的是一座可動態變化的森林：link(u, v) 在兩個不同分量的節點間建邊、合併成一棵樹； cut(u, v) 斷開一條直接邊、把樹分裂成兩個分量；makeRoot(v) 把 v 所在樹重新換根為 v；connected(u, v) 判斷兩節點是否連通；findRoot(v) 回傳 v 所在樹目前的根。內部忠實移植 splay tree 的 access/splay （偏好路徑動態重連 + rev 懶標記反轉）來正確回答這些查詢。

    誠實揭露：畫面呈現的是「被表示森林」（represented forest）——由畫面層獨立維護的邊集合 （link 時新增、cut 時移除，對照原始樹的真實邊），不是 splay tree 內部的 left/right/parent 指標結構。splay tree 的旋轉過程、偏好路徑（preferred path）重連、rev 懶標記傳播不在本頁視覺化 範圍內，內部仍忠實移植 Java 原始邏輯以正確回答查詢，並以雙演算法（獨立 BFS／獨立根追蹤）互證 正確性，僅「畫出來給人看」的部分做了取捨。splay 內部結構視覺化、pathSum/pathMax/updateValue 路徑 聚合查詢列入 backlog。
    固定腳本：10 個節點，先 link 建兩棵樹（1-0-2-3-4 與 5-6-7-8 分量，9 孤立）→ connected(3,2)=true（同樹）、connected(3,7)=false（跨樹，皆與獨立 BFS 互證一致）→ link(5,2) 合併兩樹 → connected(3,7)=true → makeRoot(6)、findRoot(4)=6 → cut(5,2) 斷回兩分量 → connected(3,7)=false → findRoot(4)=2（cut 內部先 makeRoot(5)，斷邊後 v=2 側自然以 2 為根，覆蓋先前 makeRoot(6) 換的根， 非硬編、忠實移植後實際執行得出）。

    操作腳本

      已執行查詢數：0 目前分量數：0
      10 個節點固定座標（兩排各 5 個），不隨 link/cut 變動；邊 ＝ 目前被表示森林的真實樹邊（link 新增、 cut 移除）。橘色（current）＝ 當前操作涉及節點；黃框（visited）＝ 本次 connected/findRoot 查詢 涉及的兩端節點；綠色（finalized）＝ link/cut 剛變更的邊端點；節點上方 root ＝ 該節點目前是 所在分量的根（依 makeRoot/link/cut 語意獨立維護，見上方誠實揭露）。

      最近一次查詢結果（lastAnswer）

      —

      已執行操作紀錄（opLog）

      Union-Find 只支援合併與查詢（不可 cut 刪邊、不可 makeRoot 換根）；本頁的 Link-Cut Tree 額外支援動態 刪邊與換根，代價是用攤銷 O(log n) 的 splay tree 森林取代 Union-Find 攤銷 O(α(n)) 的路徑壓縮森林 → 併查集/單調佇列/跳躍表