数据结构中的斐波那契堆

与二项堆一样，斐波那契堆也是树的集合。它们在很大程度上以二项堆为基础。与二项堆中的有序树不同，斐波那契堆中的树是有根但无序的。

斐波那契堆中的每个节点 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+ 浏览量

开启你的职业生涯

完成课程认证

开始