第19章 斐波那契堆
19.1 斐波那契堆结构
斐波那契堆是一系列具有最小堆序的有根树的集合，棵树都遵循最小堆性质。
相关的属性： 1.
x.p
：结点x的父结点 2.
x.child
：指向结点x的某一个孩子的指针，x的所有孩子被链接成一个环形的双向链表，称为x的孩子链表 3.
y.left,y.right
：孩子链表中的每个孩子y的左兄弟和右兄弟。如果y是仅有的一个孩子，则
y.left=y.right=y
4.
x.degree
：结点x的孩子链表中的孩子数目 5.
x.mark
：指示结点x自从上一次成为另一个结点的孩子后，是否失去过孩子。新产生的结点是未被标记的，并且当结点x成为另一个结点的孩子时，它便成为未被标记结点 6.
H.min
：指向根链表中关键字最小的那个结点 7.
H.n
：表示H中当前的结点数目 8.
t(H)
：表示H中根链表中树的数目 9.
m(H)
：表示H中已标记的结点数目
势函数：
Φ(H)=t(H)+2m(H)
19.2 可合并堆操作
创建一个新的斐波那契堆 MAKE-FIB-HEAP()过程分配并返回一个斐波那契堆对象H，其中
H..n=0,H.min=NIL
。实际代价为
O(1)
。插入一个结点： 实际代价为
O(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++
}
寻找最小结点： 可以直接通过H.min得到，实际代价为
O(1)
。两个斐波那契堆的合并 实际代价为
O(1)
。
FIB
-HEAT-UNIN(H1, H2){
H
= MAKE
-FIB-HEAP()
H
.min = H1
.min
concatenate the root
list of H2
with the root
list of H
if (H
.min == NIL)
||(H2
.min != NIL
&& H2
.min.key
< H1
.min.key)
H
.min = H2
.min
H
.n
= H1
.n
+ H2
.n
return H
}
抽取最小结点： 实际代价为
O(lgn)
。
FIB-HEAP-EXTRACT-MIN(H){
z = H.min
if z != NIL
for each child
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--
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++
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 roott list
if A[i].key < H.min
H.min = A[i]
}
FIB-HEAP-LINK(H,y,x){
remove y from the root list
of H
make y a child
of x, increamentingg x.degree
y.mark = FALSE
}
19.3 关键字减值和删除一个结点
关键字减值：
FIB
-HEAP-DECREASE(H,x,k){
if k
> x
.key
error
"new key is greater than current key"
x
.key
= k
y
= x
.p
if y
!= NIL
&& x
.key
< y
.key
CUT(H,x,y)
CASCADING
-CUT(H,y)
if x
.key
< H
.min.key
H
.min= x
}
CUT(H,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)
CASCADING
-CUT(H,z)
}
删除一个结点：
FIB
-HEAP-DELECT(H,x){
FIB
-HEAP-DECREASE(H,x,
-inf)
FIB
-HEAP-EXTRACT-MIN(H)
}
