題目
請實作支援 insert、meld、find-min、extract-min、decrease-key 與 delete 的 Fibonacci Heap。解釋根串列、父子關係、degree、mark 標記與級聯切斷如何協作，並用勢能函數說明為什麼 insert、meld、find-min、decrease-key 可以達到 O(1) 攤銷時間，而 extract-min 為 O(log n) 攤銷時間。
面試官考察點
- 能否區分實際單次成本與攤銷成本，不把 O(1) 攤銷說成每次都是 O(1)。
- 能否維護循環雙向串列、最小根指標、節點句柄與父指標。
- 能否正確實作 decrease-key 的切斷、標記與級聯切斷。
- 能否說明 Fibonacci Heap 的理論優勢、工程常數與 pairing heap、binary heap 的取捨。
參考答案
Fibonacci Heap 是一組滿足堆序的樹。根節點組成循環雙向串列，每個節點保存 parent、child、degree 與 mark。結構允許先延遲合併，extract-min 時再把根串列中的樹按 degree 合併。
insert 只需把新節點加入根串列並更新最小值；meld 把兩個根串列拼接。decrease-key 若破壞堆序，就把節點從父節點的 child 串列切下並放入根串列；如果父節點已經被切過，再遞迴級聯切斷。mark 表示節點是否已失去一個孩子，用於限制級聯損失。
extract-min 將最小根的孩子提升到根串列，刪除該根，再按 degree 反覆連結同階樹。勢能通常定義為根數加上兩倍的標記節點數。插入與 meld 增加根數但只支付常數，decrease-key 的級聯切斷減少標記節點並由勢能抵銷；extract-min 的實際連結次數受樹高限制在 O(log n)。
實作範例
以下偽程式碼只展示 decrease-key 的關鍵路徑，節點句柄由呼叫方保存。
decreaseKey(x, newKey):
if newKey > x.key: error
x.key = newKey
p = x.parent
if p is not empty and x.key < p.key:
cut(x, p)
cascadingCut(p)
if x.key < min.key:
min = x
cut(x, p):
removeFromChildList(p, x)
p.degree -= 1
addToRootList(x)
x.parent = empty
x.mark = false
cascadingCut(y):
p = y.parent
if p is empty: return
if y.mark is false:
y.mark = true
else:
cut(y, p)
cascadingCut(p)實作 extract-min 時要先安全遍歷被提升的孩子，再刪除最小根。連結同階根節點時必須更新 parent、child、degree 與 mark，最後重新掃描根串列找到新的 min。
常見誤區
- 只寫出二元堆積式陣列實作，卻聲稱支援 Fibonacci Heap 的 O(1) 攤銷 decrease-key。
- 切斷節點後忘記清空 parent 或 mark，導致下一次級聯切斷錯誤。
- 在循環雙向串列遍歷時邊刪除邊使用失效的 next 指標。
- extract-min 後只比較根節點，不把新提升的孩子納入根串列和最小值掃描。
- 只比較漸進複雜度，忽略指標跳轉、快取區域性、記憶體配置與實作複雜度。
複雜度取捨
在 decrease-key 很頻繁、需要 meld 且分析模型允許攤銷時，Fibonacci Heap 的理論優勢明顯，經典應用是改進 Prim 或 Dijkstra 的邊界分析。實際工程中 pairing heap、rank-pairing heap 或 binary heap 常因更簡單、更好的快取行為而更有競爭力。
Fibonacci Heap 的複雜度依賴節點句柄；如果呼叫方只能按鍵尋找節點，額外索引會改變設計。多執行緒環境還需要明確根串列與句柄的所有權，不能把無鎖安全性從攤銷分析中推導出來。
先驗證單節點、重複鍵、meld 空堆、連續 decrease-key 與刪除最後一個節點。再產生隨機操作序列，與參考優先佇列比較最小值和 extract-min 順序。針對級聯切斷構造節點連續失去兩個孩子的測試，確認第一次只標記、第二次才切斷。
參考資料
- MIT OpenCourseWare Fibonacci heaps 講義：勢能分析與 decrease-key、extract-min 複雜度。
- Fibonacci Heaps Revisited：級聯切斷與攤銷邊界的再分析。
- Fredman 與 Tarjan 的原始論文：Fibonacci Heap 及其網路最佳化演算法應用。
追問
為什麼 mark 節點要在勢能中算兩倍？
級聯切斷會減少一個標記節點並增加一個根節點。給標記節點兩單位勢能，可以支付清除標記和加入根串列的成本，使整段級聯的攤銷代價保持常數。
extract-min 為什麼是 O(log n) 攤銷？
刪除最小根並提升孩子後，連結過程讓每個 degree 至多保留一棵樹。堆序保證節點的 degree 與子樹規模相關，因此最大 degree 是 O(log n)，根串列整理的連結次數也受此限制。
meld 為什麼可以 O(1) 攤銷？
兩個循環根串列可以直接拼接，再比較兩個 min 指標。沒有立即合併同階樹，代價被留給未來的 extract-min。
什麼時候 binary heap 更合適？
當 decrease-key 不頻繁、需要陣列區域性、節點句柄不方便維護或團隊更看重可讀性時，binary heap 的 O(log n) 操作與簡單實作通常更合適。
如何處理 delete？
常見做法是把節點的鍵降到負無窮，再執行 extract-min；生產實作必須定義鍵域、哨兵值與句柄失效規則，避免把正常業務鍵誤當成哨兵。