算法导论 第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.最大度数的界

二、理解

1.延迟合并操作

FIB-HEAP-INSERT和FIB-HEAP-UNION只是最基础的链表合入操作，因为合并操作要尽可能地拖后

FIB-HEAP-EX