斐波那契堆

---

作者： 大树先生
博客： http://blog.csdn.net/koala_tree
GitHub：https://github.com/koalatree
2017 年 09 月 13 日

---

自《算法导论》.

斐波那契堆有两种用途：第一种，支持一系列操作，这些操作构成了所谓的“可合并堆”。第二种，斐波那契堆的一些操作可以在常数摊还时间内完成。

可合并堆的两种实现方式下各操作的运行时间。在操作时堆中的项数用n表示。

一、斐波那契堆结构

一个斐波那契堆是一系列具有最小堆序的有根树的集合。也就是说，每棵树均遵循最小堆性质：每个结点的关键字大于或等于它的父结点的关键字。

结点属性：

• x.p：指向其父结点的指针；
• x.child：指向其某一个孩子结点的指针；x结点所有的孩子链接成一个环形双向链表，称为孩子链表；
• y.left、y.right：每个孩子y包含，分别指向y的左兄弟和右兄弟，若只有一个孩子，则y.left=y.right=y；
• x.degree：结点x的孩子链表中的孩子树木；
• x.mark：结点x自从上一次成为另一个结点的孩子后，是否失去过孩子；
• H.min：用来访问给定的斐波那契堆，指向具有最小关键字的树的根结点，称为最小结点；
• H.n：表示H中当前结点数目。

势函数：

使用势方法来分析斐波那契堆操作的性能。

• $t(H)$：表示H中跟链表中树的数目；
• $m(H)$：表示H中已标记的结点数目；
• 势函数$\Phi(H)$：
  $$\Phi(H) = t(H) + 2m(H)$$

最大度数：

在一个n个结点的斐波那契堆中任何结点的最大度数都有上界$D(n)\leqslant \left\lfloor {\lg n} \right\rfloor$.

二、可合并堆操作

1. 创建一个新的斐波那契堆

过程分配并返回一个斐波那契堆对象H，其中H.n=0和H.min = NIL，H中不存在树。

由于$t(H)=0,m(H)=0$，空斐波那契堆的势为$\Phi(H)=0$，因此创建新堆的摊还代价等于他的实际代价$O(1)$。

2. 插入一个结点

Fib_heap_insert(H, x)x.degree = 0x.p = NILx.child = NILx.mark = FALSEif H.min == NILcreate a root list for H containing just xH.min = xelse insert x into H's root listif x.key < H.min.keyH.min = xH.n = H.n + 1

$t(H') = t(H)+1,m(H')=m(H)$，则增加的势能为1，实际代价为$O(1)$，摊还代价为$O(1)+1=O(1)$.

3. 寻找最小结点

通过指针H.min得到。可以在$O(1)$的实际代价内找到最小结点。

4. 两个斐波那契堆的合并

合并斐波那契堆$H_{1},H_{2}$，销毁这两个堆。

Fib_heap_union(H1, H2)H = Make_fib_heap()H.min = H1.minconcatenate the root list of H2 with the root list of Hif (H1.min == NIL) or (H2.min /= NIL and H2.min.key < H1.min.key)H.min = H2.minH.n = H1.n + H2.nreturn H

势函数变化为0，所以摊还代价等于实际代价$O(1)$。

5. 抽取最小结点

Fib_heap_extract_min(H)z = H.minif z /= NILfor each child x of zadd x to the root list of Hx.p = NILremove z from the root list of Hif z == z.rightH.min = NILelse H.min = z.rightConsolidate(H)H.n = H.n - 1return z

---

以上代码用到的合并（Consolidating）H根链表的操作，通过调用Consolidating(H)来减少斐波那契堆中树的数目。

过程重复执行以下步骤：

• 在根链表中找到两个具有相同度数的根x和y，其中，x.key <= y.key；
• 把y链接到x：从根链表中移除y，调用Fib_heap_link过程，使y称为x的孩子，该过程将x.degree属性增加1，并清除y上的标记。

使用辅助数组$A[0..D(H.n)]$记录根结点对应的度数的轨迹。如A[i] = y，那么当前的y是一个具有y.degree = i的根。

Consolidate(H)let A[0..D(H.n)] be a new arrayfor i = 0 to D(H.n)A[i] = NILfor each node w in the root list of Hx = wd = x.degreewhile A[d] /= NILy = A[d]  #another node with the same degree as xif x.key > y.keyexchange x with yFib_heap_link(H, y, x)A[d] = NILd = d + 1A[d] = xH.min = NILfor i = 0 to D(H.n)if A[i] /= NILif H.min == NILcreate a root list for H containing just A[i]H.min = A[i]else insert A[i] into H's root listif A[i].key < H.min.keyH.min = A[i]

Fib_heap_link(H, y, x)remove y from the root list of Hmake y a child of x, incrementing x.degreey.mark = FALSE

抽取最小结点的摊还代价为$O(D(n))=O(\lg n)$.

三、关键字减值和删除一个结点

1. 关键字减值

摊还时间：$O(1)$.

Fib_heap_decrease_key(H, x, k)error "new key is greater than current key"x.key = ky = x.pif y /= NIL and x.key < y.keyCut(H, x, y)Cascading_cut(H, y)if x.key < H.min.keyH.min = x

Cut(H, x, y)remove x from the child list of y, decrementing y.degreeadd x to the root list of Hx.p = NILx.mark = FALSE

Cascading_cut(H, y)z = z.pif z /= NILif y.mark == FALSEy.mark = TRUEelse Cut(H, y, z)Cascading_cut(H, z)

斐波那契堆中规定，某个结点x一旦失掉第二个孩子，就切断x与其父结点的链接，是它称为一个新的跟。

所以，如果切掉的结点是其父结点的第二个孩子，则需要进行一次级联切断（cascading cut）。

过程示意图：

2. 删除一个结点

摊还时间：$O(D(n))=O(\lg n)$.

Fib_heap_delete(H, x)Fib_heap_decrease_key(H, x, -inf)Fib_heap_extract_min(H)

$O(1)+O(D(n))=O(D(n))=O(\lg n)$.