資料結構中的斐波那契堆

與二項堆一樣，斐波那契堆也是樹的集合。它們在很大程度上以二項堆為基礎。與二項堆中的有序樹不同，斐波那契堆中的樹是有根但無序的。

斐波那契堆中的每個節點 x 都包含一個指向其父節點的指標 p[x]，以及一個指向其任何子節點的指標 child[x]。x 的子節點在稱為 x 的子列表的迴圈雙向連結串列中連結在一起。子列表中的每個子節點 y 都具有指向 y 的左右兄弟節點的指標 left[y] 和 right[y]。如果節點 y 是唯一子節點，則 left[y] = right[y] = y。兄弟節點在子列表中出現的順序是任意的。

斐波那契堆示例

此斐波那契堆 H 由五堆斐波那契堆和 16 個節點組成。帶箭頭線的線表示根列表。列表中的最小節點由 min[H] 表示，其值為 4。

對計算最小生成樹、查詢單源的最短路徑等問題的漸近快速演算法對斐波那契堆的本質利用非常充分。

阿爾納布 · 查克拉博蒂

更新日期： 2020 年 8 月 10 日

1000+ 瀏覽量

開啟你的職業生涯

完成課程認證

開始