Question

1.斐波那契堆

斐波那契堆是可合并堆

在不涉及删除的操作（除去 EXTRACT 和 DELETE）中，操作仅需 O(1) 的平摊运行时间

当 EXTRACT 和 DELETE 的操作数目较小时斐波那契堆能得到较好的运行效率。

斐波那契堆不能有效地支持 SEARCH 操作

用于解决诸如最小生成树和寻找单源最短路径等问题的快速算法都要用到斐波那契堆。

2.斐波那契堆的结构

斐波那契堆由一组最小堆构成，这些最小堆是有根的无序树。

结点结构：

key: 关键字，作为排序、判断结点大小的标准

left, right：用于维护双链表，所有的根结点形成一个双链表，每个结点的孩子们形成双链表

parent, child : 维护父子关系

mark : 这个域与维护堆结构无关，只与具体的算法策略有关，不在这里讲

degree： 记录该结点有几个孩子

斐波那契堆

n：堆中结点的个数

min：批向最小的结点

3.可合并堆

引理 19.1 中给出的二项树的性质对无序二项树仍然成立 P278

有 n 个结点 FibHeap，结点的最大度数 D(n) = lgn(向下取整)

将合并堆的操作尽可能地推后

4.最大度数的界

在一个包含 n 个结点的斐波那契堆中，结点的最大度数 D(n) 为 O(lgn)