『数据结构』Fibonacci-heap

1. 结构

斐波那契堆是一系列具有最小堆序的有根树的集合, 同一代(层)结点由双向循环链表链接, 为了便于删除最小结点, 还需要维持链表为升序, 即nd<=nd.right(nd==nd.right时只有一个结点或为 None), 父子之间都有指向对方的指针.

结点有degree 属性, 记录孩子的个数, mark 属性用来标记(为了满足势函数, 达到摊还需求的)

还有一个最小值指针 H.min 指向最小根结点

2. 势函数

下面用势函数来分析摊还代价, 如果你不明白, 可以看摊还分析

$\Phi(H) = t(H) + 2m(h)$
t 是根链表中树的数目,m(H) 表示被标记的结点数

最初没有结点

3. 最大度数

结点的最大度数(即孩子数)$D(n)\leqslant \lfloor lgn \rfloor$, 证明放在最后

4. 操作

4.1. 创建一个斐波那契堆

$O(1)$

4.2. 插入一个结点

1
2
3
4
5
6
7
8
9
nd = new node
nd.prt = nd.chd = None
if H.min is None:
creat H with nd
H.min = nd
else:
insert nd into H's root list
if H.min<nd: H.min = nd
H.n +=1

摊还代价为$O(1)$

4.3. 寻找最小结点

直接用 H.min, $O(1)$

4.4. 合并两个斐波那契堆

1
2
3
4
5
def union(H1,H2):
if H1.min ==None or (H1.min and H2.min and H1.min>H2.min):
H1.min = H2.min
link H2.rootList to H1.rootList
return H1

易知 $\Delta \Phi = 0$

4.5. 抽取最小值

抽取最小值, 一定是在根结点, 然后将此根结点的所有子树的根放在 根结点双向循环链表中, 之后还要进行树的合并. 以使每个根结点的度不同,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def extract-min(H):
z = H.min
if z!=None:
for chd of z:
link chd to H.rootList
chd.prt = None
remove z from the rootList of H
if z==z.right:
H.min = None
else:
H.min = z.right
consolidate(H)
H.n -=1
return z

consolidate 函数使用一个 辅助数组degree来记录所有根结点(不超过lgn)对应的度数, degree[i] = nd 表示.有且只有一个结点 nd 的度数为 i.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def consolidate(H):
initialize degree with None
for nd in H.rootList:
d = nd.degree
while degree[d] !=None:
nd2 = degree[d]
if nd2.degree < nd.degree:
nd2,nd = nd,nd2

make nd2 child of nd
nd.degree = d+1
nd.mark = False # to balace the potential

remove nd2 from H.rootList
degree[d] = None
d+=1
else: degree[d] = nd
for i in degree:
if i!=None:
link i to H.rootList
if H.min ==None: H.min = i
else if H.min>i: H.min = i

时间复杂度为$O(lgn)$ 即数组移动的长度, 而最多有 lgn个元素

4.6. 关键字减值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def decrease-key(H,x,k):
if k>x.key: error
x.key = k
y=x.p
if y!=None and x.key < y.key:
cut(H,x,y)
cascading-cut(H,y)
if x.key < H.min.key:
H.min = x
def cut(H,x,y):
remove x from the child list of y, decrementing y.degree
add x to H.rootList
x.prt = None
x.mark = False

def cascading-cut(H,y):
z- y,prt
if z !=None:
if y.mark ==False:y.mark = True
else:
cut(H,y,z)
cascading-cut(H,z)

4.7. 删除结点

1
2
decrease(H,nd, MIN)
extract-min(H)

5. 最大度数的证明

这也是斐波那契这个名字的由来,
$D(n)\leqslant \lfloor lgn \rfloor$

文章目录
  1. 1. 1. 结构
  2. 2. 2. 势函数
  3. 3. 3. 最大度数
  4. 4. 4. 操作
    1. 4.1. 4.1. 创建一个斐波那契堆
    2. 4.2. 4.2. 插入一个结点
    3. 4.3. 4.3. 寻找最小结点
    4. 4.4. 4.4. 合并两个斐波那契堆
    5. 4.5. 4.5. 抽取最小值
    6. 4.6. 4.6. 关键字减值
    7. 4.7. 4.7. 删除结点
  5. 5. 5. 最大度数的证明
<--!>