斐波那契堆

在本文中，我们将学习斐波那契堆，它的属性，优点，以及稍后的实现：在讨论斐波那契堆之前，让我们先快速回顾一下构建斐波那契堆所使用的思想。

什么是数据结构中的堆？

堆是用于表示父子关系的抽象数据类型：堆分为最小堆和最大堆。

1. 最小堆是一棵树，其中所有节点，父节点的键值必须小于子节点的键值。
2. 最大堆是一棵树，其中所有节点，父节点的键值必须大于子节点的键值。

什么是数据结构中的循环双向链表？

双向链表是单向链表的改进版本。双向链表中的每个节点包含两个指针：左指针和右指针。左指针指向其左侧节点，右指针指向其右侧节点。最后一个节点的右指针指向第一个节点，第一个节点的左指针指向最后一个节点。下图展示了循环双向链表的构成。

现在让我们讨论斐波那契堆。

定义斐波那契堆

斐波那契堆 - 斐波那契堆定义为由根节点树组成的集合，其中所有树都必须满足最小堆的属性。也就是说，对于所有节点，父节点的键值应大于子节点的键值。（注意：这里原文表述有误，应为父节点键值小于子节点）

给出的图是斐波那契树的示例。

上述斐波那契堆包含五个根节点最小堆序的树，共有 14 个节点。最小堆序树意味着满足最小堆属性的树。虚线显示了根节点列表。斐波那契堆中的最小节点是具有键值 3 的节点，由指针 FH-min 指向。

这里，18、39、26 和 35 是标记节点，意味着它们失去了一个子节点。斐波那契序列的势能 = 根节点树的数量 + 标记节点数量的 2 倍 = 5 + 2 * 4 = 13。

现在让我们观察上面的示例，了解斐波那契堆的完整表示。

在上图中，我们可以看到每个节点包含四个指针：parent 指向父节点（向上），child 指向子节点（向下），left 和 right 指针指向兄弟节点（横向）。

斐波那契堆的属性

1. 它可以有多棵相同度数的树，并且每棵树不一定需要有 2^k 个节点。
2. 斐波那契堆中的所有树都是根节点树，但不是有序的。
3. 所有根节点和兄弟节点都存储在一个独立的循环双向链表中。
4. 节点的度数是其子节点的数量。节点 X -> 度数 = X 的子节点数量。
5. 每个节点都有一个 mark 属性，值为 TRUE 或 FALSE。FALSE 表示节点没有子节点。TRUE 表示节点失去了一个子节点。新创建的节点标记为 FALSE。
6. 斐波那契堆的势能函数为 F(FH) = t[FH] + 2 * m[FH]
7. 斐波那契堆 (FH) 具有以下一些重要的技术细节：
   1. min[FH] - 指针指向斐波那契堆中的最小节点
   2. n[FH] - 表示节点数量
   3. t[FH] - 表示根节点树的数量
   4. m[FH] - 表示标记节点的数量
   5. F(FH) - 势能函数。

斐波那契堆上执行的各种操作的时间复杂度如下表所示：

1. 创建斐波那契堆

在空的斐波那契堆 (FH) 中

根节点树的数量 t(FH) = 0，

最小节点 FH -> min = NIL，

节点数量 FH -> n = 0，

标记节点数量 FH -> m = 0，并且

空斐波那契堆的势能 ?(FH) = 0。

通过 MAKE-FIB-HEAP 创建，它分配并返回斐波那契堆对象 FH，摊销成本为 O(1)，等于其实际成本。

插入节点

下面是 INSERT-FIB-HEAP 的伪代码，它将节点 x 插入斐波那契堆 FH。假设节点 x 已经分配，并且 x -> key 已经填充。

INSERT_FIB_HEAP (FH, X) 伪代码的逐行解释

1. 初始化节点 x 的度数 = 0
2. 初始化节点 x 的父节点 = NIL
3. 初始化节点 x 的子节点 = NIL
4. 将 x 的 mark 属性设置为 FALSE
5. If 条件检查斐波那契堆 (FH) 是否为空。
6. 如果是，则创建一个新的根节点列表并将 x 添加到其中。
7. 将新添加的 x 设置为最小节点。
8. 如果 if 条件失败
9. 将 x 插入根节点列表。
10. 检查 x -> key 是否小于 FH -> min。
11. 如果是，则通过更新 FH -> min = x 将 x 设置为 FH 的最小节点。
12. 最后一行，它将 FH 的节点数量增加 1。

2. 合并两个斐波那契堆

下面的伪代码简单地连接斐波那契堆 FH1 和 FH2 的根节点列表，并在过程中销毁两者，确定最小节点并返回新的斐波那契堆 FH。

UNION-FIB-HEAP (FH1, FH2) 伪代码的逐行解释

1. 创建一个新的根节点列表 FH
2. 设置 min -> FH = min -> FH1；FH 的最小节点现在是 FH1 的最小节点。
3. 将 FH2 的根节点列表连接到 FH 的根节点列表。
4. 检查 min -> FH1 是否为 null，min -> FH2 是否为 null，以及 min -> FH2 是否小于 min -> FH1。
5. 如果是，则设置 min -> FH = min -> FH2。
6. FH 中的节点数量 = FH1 中的节点数量 + FH2 中的节点数量。
7. 返回 FH。

3. 提取最小节点

最小节点的提取是斐波那契堆上最复杂的操作之一。它也是根节点列表中延迟的合并树工作最终发生的地方。下面的伪代码提取斐波那契树的最小节点。为方便使用，代码假定当一个节点从链表中移除时，链表中的指针会更新，但提取节点中的指针不会。此外，它调用辅助过程 CONSOLIDATE，我们稍后会看到。

EXTRACT-MIN-FIB-HEAP (FH) 伪代码的逐行解释

1. 将 min 指针保存在 Y 中。
2. 检查斐波那契堆是否为空。
3. 如果不为空，则为 Y 的所有子节点运行一个循环。
4. 将 Y 的子节点添加到根节点列表中。
5. 设置所有子节点的父节点属性 = NIL。
6. 从根节点列表中删除 Y 节点。
7. 如果 Y 的右指针等于 Y，则意味着它是斐波那契堆中唯一的节点。
8. 如果 Y 是唯一的节点，则设置 FH -> min = NIL。斐波那契堆现在为空。
9. 如果根节点列表中还有其他节点，则执行 Else 部分。
10. 设置 min -> FH = Y -> Right；现在，min 指向根节点列表中 Y 右侧的一个不同的节点（注意：根节点列表是一个循环双向链表）。
11. 调用 CONSOLIDATE (FH) 函数，我们将在下面讨论。
12. 将 FH 的节点数量减 1。
13. 返回 Y。

CONSOLIDATE (FH) 伪代码的逐行解释：2544

1. 在第 1 行，它创建一个大小为 D (FH -> N) 的新数组。

2. 在第 2 行和第 3 行，它在 A 的所有索引处填充 NIL。

3. - 在第 4 到 15 行，它对根节点列表中的所有节点执行相同的过程。它选择根节点列表中的每个节点 'W' 并将其存储在 'X' 中。然后，它将 X 的度数存储在 d 中，并运行一个 while 循环，如果索引 d 处不为 NIL。但最初，所有值都是 NIL，因此它不会执行，并且在第 14 行，它将 'X' 存储在索引 d 处。现在，while 的目的是检查根节点列表中是否有任何节点的度数与 'X' 相同。

在 for 循环的第二次迭代中，它从根节点列表中选择另一个节点并将其存储在 X 中，将其度数存储在 d 中。如果根节点列表中存在与 'X' 度数相同的节点，则 while 条件变为真。假设 while 循环的条件为真。现在，它将与 'X' 度数相同的节点存储在 Y 中，并检查哪个节点的键值更大。如果 Y 的键值大于 X 的键值，则交换它们，并调用LINK-FIB-HEAP (FH, Y, X) 将 Y 移除出根节点列表，使其成为 X 的子节点，然后将 X 的度数增加一。

在第 12 行，它移除数组中索引 d 处的元素，并将 d 的值增加 1。

代码的整个思想是在根节点列表中保留每个度数恰好一个节点，并将其他节点作为它们的子节点，同时不违反斐波那契堆的条件。

4. 在第 16 到 24 行，它为数组中存储的所有节点运行一个 for 循环。首先，它检查索引 I 处的数组中是否存在元素。如果存在，则执行其他代码。现在，它检查 FH 的 min 是否为 NIL。如果是，则创建一个根节点列表并将 A[I] 存储在其中，并将 FH -> min 指向它。如果不是，则将 A[I] 插入根节点列表，并将其键值与 min -> key 进行比较。哪个键值最小，FH -> min 将指向其中最小的。

LINK-FIB-HEAP (FH, Y, X) 伪代码的逐行解释

1. 它从根节点列表中移除 Y。

2. 使 Y 节点成为 X 的子节点，并将 X 的度数增加 1。

3. 将 Y -> mark 设置为 FALSE。

4. 减小键值

斐波那契堆上的减小键值操作可以在 O(1) 的摊销时间内完成。在下面的伪代码中，我们假设从链表中移除节点不会改变被移除节点中的任何结构属性。

1. 是实际的斐波那契堆，并且
2. 表示将键值 45 的节点减小到 15 后的堆。

DECREASE-Key-FIB-HEAP (FH, X, K) 伪代码的逐行解释

1. 在第 1 到 2 行，它检查输入的键值是否大于现有键值。如果是，程序终止，斐波那契堆中不会有任何更改。

2. 在第 3 行，更新 X 的键值；现在 X -> Key 等于 k。

3. 在第 4 行，它将 X 的父节点存储在 Y 中。

4. 在第 5 行，当且仅当节点 X 不属于根节点列表（即存在其父节点）且 X 的键值小于 Y 的键值时，if 条件才为真。

5. 在第 6 行，它调用 CUT (FH, X, Y) 将 X 从 F 中移除并添加到根节点列表。

6. 在第 7 行，它调用 CASCADING-CUT (FH, Y) 将 Y 标记为 True，或将其从链表中移除并添加到根节点列表。

7. 在第 8 行，它检查 X 的键值是否小于 FIB -> min -> Key。

8. 在第 9 行，如果条件满足，则将 X 设置为斐波那契堆的最小节点。

CUT (FH, X, Y) 伪代码解释

在上面的伪代码中，它首先找到 Y 的父节点并将其存储在 Z 中。然后，它检查 Y 是否在根节点列表中。如果不在，意味着 Z 不等于 NIL。再次，它检查 Y 是否被标记。如果标记为 FALSE，则将其更改为 TRUE，然后控制返回到 FIB-DECREASE-KEY。如果标记为 TRUE，则从 Z 中移除 Y 并将 Y 放入根节点列表，并重复相同的过程，直到找到一个未标记的父节点。

5. 删除节点

从一个有 n 个节点的斐波那契堆中删除节点可以在 O(D(n)) 的摊销成本时间内完成。在下面的伪代码中，我们假定堆中没有 -infinity 键值。

DECREASE-KEY-FIB-HEAP (FH, X, -∞) 将 X 的键值减小到可能的最小值，即 -infinity。EXTRACT-MIN-HEAP 函数从斐波那契堆中移除 X。可以得出结论，DELETE-FIB-HEAP 的摊销成本是 DECREASE-KEY-FIB-HEAP (O(1)) 的摊销成本和 EXTRACT-MIN-HEAP (O(D(n))) 的摊销成本之和。