第20章：斐波那契堆
一、综述
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)
二、理解
1.延迟合并操作
FIB-HEAP-INSERT和FIB-HEAP-UNION只是最基础的链表合入操作，因为合并操作要尽可能地拖后 FIB-HEAP-EXTRACT-MIN除了要完成本职工作外，还要作合并调整
2.合并调整操作
CONSOLIDATE是作合并调整的函数 它将度数相同的根链接起来，直到对应每个度数至多只有一个根 遍历每一个根结点去判断，如果两个根结点的度是一样的，让大的结点作为小的结点的孩子
3.mark的作用
为了防止堆太宽，需要策略来调整堆，使根结点成为别的根结点的孩子，该策略就是CONSOLIDATE 同理，为了防止堆太深，也需要有相应的策略去调整，在适当的时候，把某个结点的孩子变成根 这一策略就是CUT和CASCADING-CUT，mark在实现这一策略的过程中起到辅助作用。 原理：当一个非根结点被切掉了2个孩子，就把它升为根结点 在删除一个结点时，怎么区分是第一个被删除的孩子，还是第二个？此时需要用mark来标记
4.P300那句话
因为翻译不好，严重影响理解 一旦第二个孩子也失掉后，x与其父结点之间的联系就被切断了，并成为一个新根。 原文：As soon as the second child has been lost, we cut x from its parent, making it a new root.
三、改进
1.命名
mark的命名不能体现它的作用，影响理解，如果换一个好一点的名字，就不用那么大段的文字去说明 外部函数不需要FIB-HEAP-这样的前缀，因为本来就是为它写的接口 内部函数的名字要说明函数的作用，因为内部函数是被自己调用的，不要给自己添麻烦
2.分解函数
提取了一些对双链表的常用操作
3.合并函数
CUT和CASCADING-CUT合并成一个函数，因为它们其实是一个功能，就是根据策略把孩子结点升为根结点
4.参数和返回值
CUT和CASCADING-CUT中的x和y是父子关系，而且重点是子，父是只为了方便处理，不需要作为参数传进来，在函数里面重新获取一个就可以了。多传一个函数，就一个出错源 对于带参数的函数，增加一返回值。用于告知调用者是否成功，或什么原因导致失败
5.功能
FIB-HEAP-DECREASE-KEY和FIB-HEAP-DELETE这两个函数作用不大。 因为它们的入参是node*。要想调用这两个函数，就必须先获取目标结点的指针。 可是没有一个接口返回指向结点的指针，怎么找到我的目标结点的指针呢？ 调用者必须自己在创建结点后保持这个结点，这样不合理
四、代码
1.FibHeap.h 2.FibHeap.cpp 3.测试用例
Last updated