斐波那契堆(Fibonacci Heap)

定义

斐波那契堆(Fibonacci Heap)由 Fredman 和 Tarjan 于 1984 年提出,是由一组满足最小堆性质的树构成的森林结构,其名称来源于分析中节点子树规模的下界与斐波那契数列有关。

原理

插入和合并只是把新树挂入根链表,均摊 O(1);减键(decrease-key)把违反堆序的子树剪下放入根表,并通过"级联剪切"限制每个节点最多失去一个孩子;删除最小值时才做真正的整理,把相同度数的树两两合并,均摊 O(log n)。整套分析依赖势能法。

应用

斐波那契堆的意义主要在理论:它使 Dijkstra 最短路达到 O(E + V log V),Prim 最小生成树同样受益。实际工程中因常数大、实现复杂、缓存不友好,常被二叉堆、配对堆或多叉堆替代。

优缺点

优点是插入、合并、减键均摊 O(1),理论最优;缺点是实现繁琐(双向循环链表、标记位、级联剪切),实际性能往往不如简单结构。