介绍
- 斐波那契堆支持一系列操作，这些操作构成了所谓的“可合并堆”。同时，斐波那契堆的一些操作可以在常数摊还时间内完成。
操作 二叉堆(最坏情形) 斐波那契堆(摊还)
MAKE-HEAP Θ(1) Θ(1)
INSERT Θ(lgn) Θ(1)
MINIMUM Θ(1) Θ(1)
EXTRACT-MIN Θ(lgn) O(lgn)
UNION Θ(n) Θ(1)
DECREAS-KEY Θ(lgn) Θ(1)
DELETE Θ(lgn) O(lgn)
-
从理论上讲，当DELETE和EXTRACT-MIN数目相比于其它操作小得多时，斐波那契堆尤其适用。一些问题(如计算最小生成树和寻找单源最短路径必不可少地要用到斐波那契堆)
-
从实际角度看，对于大多数应用，斐波那契堆的常数因子和编程复杂性使得它比起普通二叉(或k叉)堆并不那么适用。
19.1 斐波那契堆结构
-
一个斐波那契堆是一系列具有最小堆序的有根树的集合。(每棵树均遵循最小堆性质，每个结点的关键字大于等于它的父结点关键字)
-
每个结点x饱含一个指向它父结点的指针x.p和一个指向它某一个孩子的指针x.child, x的所有孩子被连接成一个环形的双向链表。(child list)
-
x.degree: 结点x的孩子链表中的孩子数目。
-
x.mark: 结点x自从上一次成为另一个结点的孩子后，是否失去过孩子。
-
H.min指向具有最小关键字的树的根结点。如果不止一个根结点有最小关键字，则他们都可能成为最小结点。如果H是空，H.min为NIL。
-
H.n表示H中当前的结点数目。
-
势函数: 用t(H)表示H中根链表中树的数目，m(H)表示已标记的结点数目，定义 Φ(H) = t(H) + 2m(H)
-
如果仅仅是支持可合并堆操作，D(n) <= floor(lgn). 当支持DECREASE-KEY和DELETE操作，D(n) = O(lgn)
19.2 可合并堆操作
-
斐波那契堆上的一些可合并操作要尽可能长地延后执行。不同操作可以进行性能平衡。
-
无论根链表在执行EXTRACT-MIN前是什么样子，执行完该操作后，根链表中的每个结点要有一个与根链表其它结点不同的度数。根链表规模最大是D(n)+1.
-
插入一个结点
FIB-HEAP-INSERT(H, x)
x.degree = 0
x.p = NIL
x.child = NIL
x.mark = FALSE
if H.min == NIL
create a root list for H containing just x
H.min = x
else insert x into H's root list
if x.key < H.min.key
H.min = x
H.n += 1
摊还代价为O(1)
- 两个斐波那契堆的合并
FIB-HEAP-UNION(H1, H2)
H = MAKE-FIB-HEAP()
H.min = H1.min
concatenate the root list of H2 with the root list of H
if (h1.min == NIL) or (H2.min != NIL and H2.min.key < H1.min.key)
H.min = H2.min
H.n = H1.n + H2.n
return H
- 抽取最小结点: 本节所介绍的操作中最复杂的一个
FIB-HEAP-EXTRACT-MIN(H)
z = H.min
if z != NIL
for each child x of z
add x to the root list of H
x.p = NIL
remove z from the root list of H
if z == z.right
H.min = NIL
else H.min = z.right
CONSOLIDATE(H)
H.n -= 1
return z
CONSOLIDATE(H)
let A[0..D(H.n)] be a new array
for i = 0 to D(H.n)
A[i] = NIL
for each node w in the root list of H
x = w
d = x.degree
while A[d] != NIL
y = A[d]
if x.key > y.key
exchange x with y
FIB-HEAP-LINK(H, y, x)
A[d] = NIL
d += 1
A[d] = x
H.min = NIL
for i = 0 to D(H.n)
if A[i] != NIL
if H.min == NIL
create a root list for H containing just A[i]
H.min = A[i]
else insert A[i] into H's root list
if A[i].key < H.min.key
H.min = A[i]
FIB-HEAP-LINK(H, y, x)
remove y from the root list of H
make y a child of x, incrementing x.degree
y.mark = False
抽取最小结点的摊还代价为O(lgn)
- 练习19.2-1 给出图19-4中调用FIB-HEAP-EXTRACT-MIN后得到的斐波那契堆
运行算法……
19.3 关键字减值和删除一个结点
- 关键字减值
FIB-HEAP-DECREASE-KEY(H, x, k)
if k > x.key
error "new key is greater than current key"
x.key = k
y = x.p
if y != NIL and x.key < y.key
CUT(H, x, y)
CASCADING-CUT(H, y)
if x.key < H.min.key
H.min = x
CUT(H, x, y)
remove x from the child list of y, decrementing y.degree
add x to the root list of H
x.p = NIL
x.mark = FALSE
CASCADING-CUT(H, y)
z = y.p
if z != NIL
if y.mark == FALSE
y.mark = TRUE
else CUT(H, y, z)
CASCADING-CUT(H, z)
