Data Structure Note(VI) —— Advance-Data-Structure

Prologue

　　这是数据结构大杂烩系列的第六篇文章。在这篇文章中，我们将一起学习算法导论中高级数据结构的部分，内容主要是书中部分知识的整理和记录。

B-Tree

Definition

　　B树是为磁盘或其他直接存取的辅助存储设备而设计的一种平衡搜索树。B树是具有以下性质的有根树:

1. 每个结点有以下属性
   1. x.n，表示当前结点中的关键字个数
   2. x.n个关键字本身\(x.key_1,x.key_2,…,x.key_{x.n}\)，以非降序存放
   3. x.leaf 一个布尔值，表示x是否为叶结点
2. 每个内部结点还包含x.n+1个指向其孩子的指针\(x.c_1,x.c_2,…,x.c_{x.n+1}\)。叶子结点没有孩子
3. 关键字\(x.key_i\)对存取在各子树中的关键字进行分割，由于有x.n个key，我们可以得到x.n+1个区间，即x.n+1个孩子。另\(x.c_i\)表示第i个孩子，\(k_i\)表示这个以这个孩子为根的结点的子树，则:\(k_1<=x.key_1<=k_2<=x.key_2<=…<=x.key_{x.n}<=k_{x.n+1}\)
4. 每个叶结点具有相同的深度，即树高h
5. 每个节点所包含的关键字个数具有上界和下界。用一个被成为B树最小度数的固定整数t(t>=2)来表示。
   1. 除了根节点外，每个结点至少有t-1个关键字。即除了叶子结点外的内部结点都至少有t个孩子。
   2. 每个结点至多可包含2t-1个关键字。即，一个内部结点至多有2t个孩子。当一个结点恰好有2t个孩子时，我们称该结点是满的

　　另外，B+树是指将所有卫星数据都存储在叶结点中的树，内部结点只需存放关键字和指向孩子的指针。

Search & Create

　　B树的搜索基本上和BST一样，区别仅仅在于B树的搜索不是两个分支，而是x.n+1个

B-TREE-SEARCH(x, k):
i = 1
while i <= x.n and k > x.key[i]
    i = i + 1
if i <= x.n and k == x.key[i]
    return (x,i)
else if x.leaf
    return NIL
else DISK-READ(x.c[i])
    return B-TREE-SEARCH(x.c[i], k)

　　树高为\(O(log_tn)\)，故搜索耗时为\(O(tlog_tn)\)。另外，这里事实上是可以做一点小优化的。如果B树的最小度数t比较大的话，我们可以采用二分查找的方式，进一步降低复杂度，耗时变为\(O(logn)\)
　　为了构造一棵B树，我们需要先定义一个辅助函数ALLOCATE-NODE，它负责分配一个新的结点。接下来我们可以创建一棵空的B树。

B-TREE-CREATE(T):
x = ALLOCATE-NODE()
x.leaf = TRUE
x.n = 0
DISK-WRITE(x)
T.root = x

Insert

　　B树中插入一个关键字还是比较复杂的，因为我们需要保证B树除根结点外的内部结点的度数在一定范围内。插入过程中，由于结点为满时，我们不能再插入。因此，我们需要一个分裂操作，将已满结点(2t-1个关键字)分裂为两个各含t-1个关键字的结点，中间的关键字被提到父亲结点，以产生一个新的孩子指针。(这里比较复杂，建议结合图片理解)
　　在插入的过程中，我们沿着树向下查询，如果子树的关键字已满，则对其进行分裂。这样我们就能保证在插入的时候不会出现往已满结点插入关键字的情况。
　　分裂如下:

// y=x.c[i]为已满的结点，即y具有2t-1个关键字
B-TREE-SPLIT-CHILD(x, i)
// 新开辟一个结点z
z = ALLOCATE-NODE
y = x.c[i]
z.leaf = y.leaf
z.n = t-1
// 复制y的右边t-1个关键字到z中
for j=1 to t-1
    z.key[j] = y.key[j+t]
// y是非叶子结点的话，孩子指针也要复制
if y.leaf == false
    for j = 1 to t
        z.c[j] = y.c[j+t]
y.n = t-1
// 移动x右边的关键字，空出一个位置留给将被提上来的关键字
for j = x.n+1 down to i+1
    x.c[j+1] = x.c[j]
x.c[i+1] = z
for j = x.n downto i
    x.key[j+1] = x.key[j]
x.key[i] = y.key[i]
x.n = x.n +1
DISK-WRITE(y,z,x)

　　有了分裂的操作，插入操作就容易了很多。我们只需要保证树根不满即可。后面遇到已满的结点时，只需对该结点进行split操作，然后再进行访问即可。

B-TREE-INSERT(T,k):
r = T.root
if r.n == 2t-1
    s = ALLOCATE-NODE()
    T.root = s
    s.leaf = FALSE
    s.n = 0
    s.c[1] = r
    B-TREE-SPLIT-CHILD(s,1)
    B-TREE-INSERT-NONFULL(s,k)
else B-TREE-INSERT-NONFULL(r,k)

　　接下来，插入的时候保证非满。

B-TREE-INSERT-NONFULL(x,k):
i = x.n
// 叶子结点时，直接找到对应位置插入即可
if x.leaf
    while i >= 1 and k < x.key[i]
        x.key[i+1] = x.key[i]
        i = i-1
    x.key[i+1] = k
    x.n = x.n+1
    DISK-WRITE(x)
else while i >= 1 and k < x.key[i]
        i = i-1
    i = i + 1
    DISK-READ(x.c[i])
    // 如果已满，需要分裂，注意到分裂后i可能需要+1
    if (x.c[i].n) == 2t-1
        B-TREE-SPLIT-CHILD(x,i)
        if k > x.key[i]
            i = i + 1
    B-TREE-INSERT-NONFULL(x.c[i],k)

Remove

　　删除操作本身还是要比插入要难一些。我们删除时，会发生两个问题。一是删除关键字后，当前结点的孩子数量就要减少，如果当前结点不是叶子结点的话会出问题，解决方案是类似BST，我们寻找一个前驱或者后继来替代当前结点。二是删除结点后，有可能导致当前结点的关键字数量小于t-1，从而破坏了B树的性质，因此，我们需要在一定的条件下对B树的结点进行一些合并的操作。
　　在实现删除操作时，我们加强了一下条件，保证当前结点x的关键字数量至少为t。在删除过程中，分以下几种情况讨论:

1. 如果关键字k在结点x中，并且x是叶结点，直接从x中删除k
2. 如果关键字k在结点x中，并且x是内部结点，则做以下操作:
   1. 如果结点x中在k前面的子结点至少包含t个关键字，则找出k在以y为根的子树中的前驱k’。递归地删除k’，并在x中用k’代替k。
   2. 对称地，如果y少于t个关键字，则检查关键字k后面的子结点z。如果z至少有t个关键字，则找出k在以z为根的子树中的后继k’。递归地删除k’，并用k’替代k
   3. 否则，y和z都只有t-1个关键字，将k和z全部合并进y，这样x失去了一个关键字和一个孩子，并且y现在包含2t-1个结点，递归地从y中删除k
3. 如果关键字k不再当前内部结点中，则确定可能包含k的子树的根x.c[i]。如果x.c[i]只有t-1个关键字，执行以下两个步骤来保证x.c[i]包含t个关键字
   1. 如果x.c[i]只有t-1个关键字，但相邻的一个兄弟节点至少包含t个关键字，则将x中某一个结点降至x.c[i]中，并将x.c[i]的相邻兄弟的一个关键字升到x，并将相应的孩子指针移到x.c[i]中。
   2. 如果x.c[i]以及相邻的兄弟都只包含t-1个关键字，则将x.c[i]与一个兄弟合并。

　　尽管这个操作有些复杂，逻辑还是比较清晰的，且复杂度依然为O(h)。伪代码如下:

B-TREE-REMOVE(x, k):
if k in x.key
    // 情况1
    if x.leaf == True
        remove k in x.key
    else
        index = x.key.indexOf(k)
        // 情况2.1
        if x.c[index].size >= t
            k' = find-max(x.c[index])
            x.key[index] = k'
            B-TREE-REMOVE(x.c[index],k')
        // 情况2.2
        else if x.key[index+1].size >= t
            k' = find-min(x.c[index+1])
            x.key[index] = k'
            B-TREE-REMOVE(x.c[index+1],k')
        // 情况2.3
        else
            MERGE(x.c[index], k, x.c[index+1])
// 情况3
else
    find x.c[i] that may contain k
    if x.c[i].size >= t
        B-TREE-REMOVE(x.c[i],k)
    else
        ...

Disjoint-set

　　在实际编程中，我们往往需要实现这样一类需求: 给定两个元素，判断它们是否位于同一个集合。这种时候，我们就需要用到不相交集合的数据结构，它维护了一个不相交的动态集的集合，\(\delta = {S_1, S_2, S_3,…,S_k}\)，每个集合\(S_i\)对应有一个代表，它是这个集合中的任意一个元素。这种数据结构支持以下功能:
　　MAKE-SET(x): 创建一个新的集合。由于只有一个元素 x，x 是集合的代表
　　UNION(x,y): 将包含x和y的两个动态集合合并为一个新的集合 S。并且，我们需要在\(\delta\)中将包含 x 和 y 的两个动态集合删掉，并加入合并后的新集合 S
　　FIND-SET(x): 返回 x 所在的动态集合的代表
　　在OI中，我们经常用到的并查集就是这样的一种数据结构。

Minimal Spanning Tree

　　前面的定义也许有点难理解，我们还是来看并查集的一个重要应用——最小生成树吧。我们在贪心算法的章节中知道，Kruskal 算法实现过程中，需要查询当前选择的两条边是否位于同一颗树中。我们使用 fa[x] 数组表示当前元素的父亲，当 x 的父亲是自己时，说明 x 为树根，即所在集合的代表。以下是实现的代码:

int fa[N];
// n为元素的个数
MAKE-SET(n):
    // 选取每个元素自身作为代表
    for i from 1 to n
        fa[i] = i;

// 查找x所在集合的代表
FIND-SET(x):
    if x == fa[x] return x
    // 这是一个路径压缩的过程，建议尝试画图理解
    return fa[x] = find(fa[x])

UNION(x, y):
    // 获取两棵树的树根，如果不相同，则将他们连接在一起。
    // 注意到事实上我们只需要连接两个集合的代表就行了，以fx为根的子树中的其他元素
    // 在进行FIND-SET的过程中会进行路径压缩，最后还是会连接到了fy
    fx = FIND-SET(x)
    fy = FIND-SET(y)
    if fx != fy:
        fa[fx] = fy

　　可以证明，使用并查集的写法，我们可以在均摊复杂度 O(1) 的时间内实现UNION，FIND—SET，MAKE—SET操作。具体证明的过程算法导论书中已经给出，这里不再进行说明。

Food-link

　　NOI2001食物链是一道很经典的并查集的题目，充分运用了不相交集合的特点解决问题。题目简单描述如下:

给定n个动物，按照1-N进行编号，每个动物都是A，B，C中的一种，但是我们并不知道它是属于哪一种。而且这三种动物满足A吃B，B吃C，C吃A这样的性质。现在给k句表述，分两种类型:
第一种是”1 X Y”，表示说X和Y是同类
第二种是”2 X Y”，表示说X吃Y
这k句表述中，有的是真的，有的是假的，当一句话满足下列三个条件之一时，就是假话:
(1) 当前的话与之前的话冲突
(2) 当前的话X或者Y比N大
(3) 当前的话表示X吃X
最后我们根据给定的n和k，需要输出假话的总数

　　表面上一看，这样一道题目似乎是很难解决的。那么我们如何使用并查集去解决呢?
　　首先我们需要解决吃与被吃的关系如何维护的问题。注意到如果 A，B，C 之间的捕食关系事实上构成了一个循环。如果我们分别用 0，1，2 标识 A，B，C，我们会惊讶地发现几种动物的捕食关系构成了一个模3意义下的加法群。如果X吃Y，那么我们可以得到\(type[X]=(type[Y]+1)%3。\)
　　但是，一个比较麻烦的例子是，现在告诉你 1 吃 2，3 吃 4，可我们并没有办法知道 1，2 和 3，4 的关系。因此我们将它们当成是两个不同的动态集合，由于我们能够使用并查集处理这两个集合内部之间的吃与被吃的关系，那么最后的问题其实就仅仅在于两个集合如何进行合并了。
　　因为需要维护和根节点的关系，我们的 FIND-SET 函数需要做适当的更改。对于当前结点 x，如果 fa[x] 不是根，那么必然需要发生路径压缩。另外，如果 x 为根，那么我们可以确信 type[x] 的值一定是 0，因为它没有发生过任何更改。因此，发生路径压缩过后，fa[x] 的 type 可能发生了更改，那么当前结点 x 的 type 也可能要做相应更改，由于构成了模3的加法群，我们就有: \(type[x] = (type[x]+type[fa[x]])%3\)

#include <stdio.h>
#include <algorithm>
#define N 50003
// type[x]维护的是x和fa[x]之间的关系
int fa[N], type[N];
int find(int x) {
    if (x == fa[x]) return x;
    int ff = find(fa[x]);
    type[x] = (type[x] + type[fa[x]]) % 3;
    return fa[x] = ff;
}
int main() {
    int n, k;
    int p, x, y, ans = 0;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
        type[i] = 0;
    }
    for (int i = 1; i <= k; i++) {
        scanf("%d%d%d", &p, &x, &y);
        if (x > n || y > n) {
            ans++;
            continue;
        }
        if (x == y) {
            if (p == 2) ans++;
            continue;
        }
        int fx = find(x), fy = find(y);
        if (fx != fy) {
            // 这个是最大的难点。
            fa[fx] = fy;
            type[fx] = (type[y] - type[x] + p - 1 + 3) % 3;
        } else {
            // 属于同一个集合，我们只需要判断是否是假话即可
            if (p == 1 && type[x] != type[y]) ans++;
            else if (p == 2 && (type[x] != (type[y] + 1) % 3)) ans++;
        }
    }
    printf("%d\n", ans);
    return 0;
}

　　注意到上面的代码中，如果 x 和 y 不在同一棵树上( fx != fy )，那么表述一定为真，并且我们需要将两棵树进行合成。由于 find 函数会进行路径压缩，在经过 find(x) 和 find(y) 后，x，y 应该是分别直接和 fx, fy 相连。为了将两棵树连在一起，这里我们直接将 fx 的父亲设置 fy，然后fx的类型需要做对应的修改。如果 p=1，那么 x 和 y 的 type 应该是相同的，为了使得 x 和 y 的 type 相同，这个时候 fx 的 type 应该变成 type[y] - type[x]，这样最后 x 点进行路径压缩后，type[x] 就和 type[y] 相等了。p=2 时，处理方法类似，经过合并后，我们就得到了上述的等式。简单的图示如下(以 p=1 为例, p=2 处理类似):

Fibonacci Heap

　　斐波那契堆是堆的一种高效实现。它支持一系列的操作，构成了实用的”可合并堆”。可合并堆支持以下操作:

1. MAKE-HEAP() : 创建一个空堆
2. INSERT(H,x) : 将一个包含关键字 x 的元素放进堆中
3. MINIMUM(H): 返回一个指向堆中最小元素的指针
4. EXTRACT-MIN(H) : 从堆中删除包含最小关键字的元素，并返回
5. UNION(H1,H2) : 合并两个堆 H1 和 H2，并返回一个新堆的指针

　　除了可合并堆的特性，斐波那契堆还支持以下操作:

1. DECREASE—KEY(H,x,k) : 将堆中的元素 x 赋予一个新的更小的关键字 k
2. DELETE(H,x) : 删除堆中的元素 x

　　我们如果把普通的二叉堆和斐波那契堆比较的话，我们会发现，斐波那契堆在很多情形下有着更好的摊还时间界。二叉堆在 UNION 操作上的时间复杂度较高，其余的操作基本效率还是可以的。因此，在需要较多的合并操作的时候，我们可以应用斐波那契堆。

操作	二叉堆(最坏情况)	斐波那契堆(摊还)
MAKE-HEAP	Θ(1)	Θ(1)
INSERT	Θ(lgn)	Θ(1)
MINIMUM	Θ(1)	Θ(1)
EXTRACT-MIN	Θ(lgn)	O(lgn)
UNION	Θ(n)	Θ(1)
DECREASE-KEY	Θ(lgn)	Θ(1)
DELETE	Θ(lgn)	O(lgn)

　　尽管，从理论上分析，斐波那契堆的性能是十分优秀的，但是在实际应用中，它适用范围并不是十分的广泛，原因除了在于斐波那契堆编程上的复杂性外，还有其各个操作较大的常数。现在，就让我们一起来看一下吧。

Basic structure

　　斐波那契堆是一系列具有最小堆性质的有根树的集合，即每个结点的关键字严格大于父结点。书中给了这样一个形象的例子:

　　从上面的那个图中我们可以看到斐波那契堆的最小堆特性。而下面那个图看起来复杂了许多，这个是斐波那契堆结构的完整版本。每个结点 x 包含指向它父亲的指针 x.p 和指向它任意某个孩子的指针 x.child (如果有的话)。并且，x 的所有孩子形成了一个环形的双向链表，称为 x 的孩子链表。孩子链表中的每一个结点 y 均有指针 y.left 和 y.right ，分别指向左右兄弟。
　　除此以外，每个结点还有以下的几个特性: x.degree 表示当前结点的孩子的数量，x.mark 表示当前结点是否被打上了标记 (后面 DECREASE-KEY 操作用到)。x.mark 表示结点 x 自从上一次成为另一个结点的孩子后，是否失去过孩子。另外，斐波那契堆还需要有一个指针 H.min 表示当前堆的集合中具有最小关键字的堆的根节点。所有的堆的根节点同样使用双向链表进行连接。H.n 表示当前堆集合中所有的结点的数量。
　　为了便于分析斐波那契堆的性能，书中采用了势函数的方式。对于一个给行斐波那契堆 H，t(H) 表示 H 中根链表元素的数目，用 m(H) 来表示 H 中已标记的结点的数目。由于 t(H), m(H) 初始时均为0，且均为整数，故满足势函数的条件。定义斐波那契堆的势函数 Φ(H) 如下:
$$\phi (H) = t(H) + 2m(H)$$

　　另外，我自己尝试了根据书中的代码写了一个 C/C++ 版的样例 (仅支持 INSERT, MINIMUM 和 EXTRACT-MIN 操作，无注释)，如果有需要的话可以参考一下。

Insert & Union

　　创建一个堆的过程是很简单的。我们只需要分配一个斐波那契堆对象即可，并且其中 H.n = 0，H.min = NIL 即可，代价为 O(1)。获取最小结点的话，只需要返回 H.min 对象，代价同样为 O(1)。
　　插入一个结点的做法也很简单，只需要将当前的结点插入根节点所在的链表即可。

FIB-HEAP-INSERT(H,x):
initialize x
...
if H.min == NIL
    H.min = x
    put x in H's root list
else
    insert x into H's root list
    if x.key < H.min.key
        H.min = x
H.n += 1

　　合并两个结点的操作也比较直接，我们只需要将其插入根链表，并更新 H.n 的值就好了。

FIB-HEAP-UNION(H1,H2):
if H1.min == NIL or H2.min == NIL
    return H1 or H2
H = MAKE-HEAP()
H.min = H1.min
add H2's root list into H
H.n = H1.n + H2.n
return H

Extract-min

　　获取并删除最小结点的操作比较复杂，涉及的情况也比较多，容易犯错。由于最小的结点一定在根链表上，当这个结点从树上移除后，其孩子需要被更新，我们采取的措施是将所有的孩子移动到根链表，然后再进行根链表的合并操作，以减少根链表中的结点数量。

FIB-HEAP-EXTRACT(H)
if H.min == NIL
    return NIL
z = H.min
for x in z.child's list
    add into H's root list
    x.p = NIL
remove z from H's root list
// z 是根链表中的唯一结点，且没有孩子
if z == z.right
    H.min = NIL
else
// 将 H.min 随便设置为一个其他的结点，然后进行合并操作
// 保证根链表中度数为 d 的结点最多只有 1 个
    H.min = H.right
    CONSOLIDATE(H)
return z

　　合并操作是斐波那契树中最难的一个点。合并的过程分为以下的两个步骤，直到根链表中每一个根都有不同的度数。

1. 在根链表中找具有相同度数的两个结点 x 和 y，假定 x.key <= y.key
2. 把 y 链接到 x: 从根链表中移除 y， 并让 y 成为 x 的孩子，清除 y 上的标记(成为了孩子)。并将 x 的度数 +1

　　为了便于合并的操作，我们使用一个数组 A 来记录根节点度数的信息。如果 A[d] = x，说明根链表中的根节点 x 的度数为 d。并且这里还有用到后面会证明的一个信息: 最大度数的上界为 D(H,n) = logn + 1

CONSOLIDATE(H):
initialize A[0...D(H,n)]
for w in H's root list
    x = w
    d = w.degree
    while A[d] != NIL
        y = A[d]
        if x.key > y.key
            swap(x, y)
        FIB-HEAP-LINK(H,y,x)
        A[d] = NIL
        d += 1
    A[d] = x

H.min = NIL
for i from 0 to D(H,n)
    if A[i] == NIL
        continue
    if H.min == NIL
        H.min = A[i]
        let A[i] be H's root list
    else
        make sure A[i] in H's root list
        if A[i].key < H.min.key
            H.min = A[i]

FIB-HEAP-LINK(H,y,x):
remove y from H's root list
insert y in x's child list
x.degree += 1
y.mark = false

　　对于这个过程，书中给出了一个很形象的图进行描述。如果能理解好这个图在干什么，相信这个操作就掌握了。此外，可以证明，这个操作的复杂度是 O(D(n))

　　在 EXTRACT-MIN 操作中，最多处理 D(n) 个孩子，再加上 CONSOLIDATE 中下面的循环同样也是 D(n)，因此复杂度为 O(D(n))。但是，CONSOLIDATE 中遍历根链表的操作，复杂度与根节点数目有关，这个时候代价不够，我们就需要从势函数中找。假设原始根链表中有 t(H) 个结点，减去抽出的结点再加上抽取出的结点的孩子，调用 CONSOLIDATE 函数时根节点最多为 t(H) + D(H) - 1。令抽取最小结点之前的势为 t(H) + 2m(H)，最多有 D(H) + 1 个结点留下，则我们得到摊还代价为:
$$
\begin{align}
& O(D(n)+t(H))+((D(n)+1)+2m(H))-(t(H)+2m(H))\\
=& O(D(n))+O(t(H))-t(H) \\
=& O(D(n))
\end{align}
$$

Decrease key & Delete

　　对于关键字减值操作，由于减值后有可能会破坏堆的特性，使得当前结点 x 的 key 比父亲要小，这个时候我们不采取旋转之类的措施，而是选择直接将当前结点放到根节点上去，保证了堆的属性不被破坏。同时，由于当前结点 x 被删除，y 的 mark 值需要做对应的处理。如果 y 还没有被删除过儿子(y.mark = false)，那么 y 的 mark 应该被设置为 true。反之，我们对 y 执行级联切断，递归处理。

FIB-HEAP-DECREAE-KEY(H,x,k):
x.key = k
y = x.p
if y != NIL and x.key < y.key
    CUT(H,x,y)
    CASCADING-CUT(y)
if x.key < H.min.key
    H.min = x

CUT(H,x,y):
remove x from y's child list
y.degree--
add x into H's root list
x.p = NIL
x.mark = FALSE

CASCADING-CUT(H,y):
z = y.p
if z == NIL
    return
if y.mark == false
    y.mark = true
else
    CUT(H,y,z)
    CASCADING-CUT(H,z)

　　同样的，使用势函数，我们可以证明，DECREASE-KEY 操作能在摊还时间 O(1) 内完成。使用 DECREASE-KEY 操作，我们可以使用类似于二叉堆的处理方法删除结点 —— 将结点 x 的 key 设置为负无穷，并且调用 EXTRACT-MIN 即可。

Proof of D(n)

　　这里要证明一个具有 n 个结点的斐波那契堆中任意结点的度数的上界 D(n) 为 O(lgn)。特别的，我们证明\(D(n)=floor(log_{\phi}n)\)，这里 Φ 指的是黄金分割率，即，\(\phi = ((1+\sqrt5) / 2)\)
　　我们知道，斐波那契数的定义如下:
$$
F_k=\begin{cases}
0,\qquad 如果 k=0 \\
1,\qquad 如果 k=1 \\
F_{k-1}+F_{k-2} \qquad 如果 k >= 2
\end{cases}
$$

　　由这个定义，我们可以的得到斐波那契数的另一种表示方式: \(F_{k+2}=1+\Sigma_{i=0}^k F_i\)。具体可以用归纳法证明。并且，同样的，使用归纳法，我们还可以证明\(F_{k+2}>=\phi^k\)
　　回到斐波那契堆上，设 x 是斐波那契堆中的任意结点，假设 x.degree = k。设\(y_1,y_2,…,y_k\)是 x 的孩子，并按照成为孩子的先后顺序排列，则我们有 \(y_1.degree >= 0，且对于i=2,3,…,k 有 y_i.degree >= i-2\)。原因是，当第 i 个节点结点插入后，\(y_1,y_2,…y_n\)已经成为了 x 的孩子了，且插入时必定满足 x 和 y 的 degree 相等，则一定有 \(y.degree = x.degree>=i-1\).此后，y 最多失去一个孩子(失去两个孩子则会被 CASCADING 操作剪除)，因此，我们有 \(y.degree >= i-2\)
　　此时，我们可以正式证明任意结点度数的上界了。设 x 为斐波那契堆的任意节点，k = x.degree，\(s_k\)表示斐波那契堆中度数为 k 任意结点 size 的最小值。则有:

$$size(x) \geq s_k \geq 2+\Sigma_{i=2}^k s_{y_i.degree} \geq 2+\Sigma_{i=2}^k s_{i-2}$$

　　这里 +2 表示的是当前结点和第一个孩子。再次使用归纳法，假设\(s_k >= F_{k+2}\)。

$$
\begin{align}
s_k &\geq 2+\Sigma_{i=2}^k s_{i-2} >= 2+\Sigma_{i=2}^k F_i = 1+\Sigma_{i=0}^k F_i \\
&= F_{k+2}　\\
&\geq \phi^k
\end{align}
$$

　　因此，我们得到了\(size(x) \geq s_k \geq F_{k+2} \geq \phi^k\)。若 n 是斐波那契堆中所有的结点的个数，则\(n \geq size(x) \geq \phi^k，即 k \leq log_{\phi}n\)
　　假设得证。

Epilogue