斐波那契堆数据结构背后的直觉是什么？

这个答案会很长，但我希望它有助于提供一些关于斐波那契堆的来源的见解。我假设您已经熟悉 binomial heaps 和 amortized analysis。

动机：为什么是斐波那契堆？

在进入斐波那契堆之前，最好先探索一下为什么我们甚至需要它们。还有很多其他类型的堆（例如 binary heaps 和 binomial heaps），那么我们为什么需要另一个堆呢？

主要原因出现在 Dijkstra's algorithm 和 Prim's algorithm。这两种图算法都通过维护一个优先级队列来工作，该队列持有具有相关优先级的节点。有趣的是，这些算法依赖于一个称为 decrease-key 的堆操作，该操作采用已经在优先级队列中的条目，然后减少其键（即增加其优先级）。事实上，这些算法的很多运行时间都可以通过调用 reduce-key 的次数来解释。如果我们可以构建一个优化减少键的数据结构，我们就可以优化这些算法的性能。在二叉堆和二项堆的情况下，reduce-key 需要时间 O(log n)，其中 n 是优先级队列中的节点数。如果我们可以将其降低到 O(1)，那么 Dijkstra 算法和 Prim 算法的时间复杂度将从 O(m log n) 下降到 (m + n log n)，这比以前更快。因此，尝试构建一个有效支持 reduce-key 的数据结构是有意义的。

考虑设计更好的堆结构还有另一个原因。将元素添加到空二进制堆时，每次插入都需要时间 O(log n)。如果我们事先知道所有 n 个元素，则可以 build a binary heap in time O(n)，但如果元素以流的形式到达，则这是不可能的。在二项式堆的情况下，插入 n 个连续元素每个都需要 O(1) 分摊时间，但如果插入与删除交错，则插入最终可能会花费 Ω(log n) 时间。因此，我们可能想要搜索一个优先队列实现来优化插入以花费 O(1) 时间。

第一步：惰性二项式堆

要开始构建斐波那契堆，我们将从二项式堆开始并对其进行修改，尝试使插入花费时间 O(1)。尝试这一点并不是那么不合理 - 毕竟，如果我们要进行大量插入而不是尽可能多的出队，那么优化插入是有意义的。

如果您还记得，二项式堆的工作原理是将堆中的所有元素存储在 binomial trees 的集合中。一棵 n 阶二叉树有 2ⁿ 个节点，堆是结构作为二叉树集合的结构，它们都服从堆属性。通常，二项式堆中的插入算法如下工作：

创建一个新的单例节点（这是一棵 0 阶树）。

如果有 0 阶树：将两棵 0 阶树合并为 1 阶树。如果有 1 阶树：将两棵 1 阶树合并为 2 阶树。如果有2 阶树：...

将两棵 0 阶树合并成一棵 1 阶树。

如果存在一阶树：将两棵一阶树合并成一棵二阶树。如果存在一棵二阶树：...

将 1 阶的两棵树合并为 2 阶的树。

如果有一棵二阶树：...

...

这个过程确保在每个时间点，每个订单最多有一个树。由于每棵树的节点数比它的顺序多，这保证了树的总数很小，这让出队运行得很快（因为我们在执行出列最小步骤后不必查看太多不同的树）。

然而，这也意味着将节点插入二项式堆的最坏情况运行时间是 Θ(log n)，因为我们可能有需要合并在一起的 Θ(log n) 树。这些树需要合并在一起只是因为我们需要在执行出队步骤时保持树的数量较少，并且在将来的插入中保持树的数量很少绝对没有任何好处。

这引入了与二项式堆的第一个不同之处：

修改1：在堆中插入节点时，只需创建一棵0阶树，并将其添加到现有的树集合中即可。不要将树木合并在一起。

我们还可以做出另一个改变。通常，当我们将两个二项式堆合并在一起时，我们会执行一个合并步骤来将它们合并在一起，以确保在结果树中每个顺序最多有一个树。同样，我们进行这种压缩以使出队速度更快，并且没有真正的理由让合并操作必须为此付出代价。因此，我们将进行第二次更改：

修改2：将两个堆合并在一起时，只需将它们所有的树合并在一起，而不进行任何合并。不要将任何树合并在一起。

如果我们进行此更改，我们很容易在入队操作上获得 O(1) 性能，因为我们所做的只是创建一个新节点并将其添加到树集合中。但是，如果我们只做这个改变而不做任何其他事情，我们就完全破坏了 dequeue-min 操作的性能。回想一下，dequeue-min 需要在移除最小值后扫描堆中所有树的根，以便找到最小值。如果我们通过在其中插入 Θ(n) 节点来添加它们，那么我们的出队操作将不得不花费 Θ(n) 时间来查看所有这些树。这是一个巨大的性能冲击......我们可以避免它吗？

如果我们的插入真的只是添加更多的树，那么我们做的第一个出队肯定会花费 Ω(n) 时间。然而，这并不意味着每个出队都必须是昂贵的。如果在执行出队后，我们将堆中的所有树合并在一起，最终每个订单只有一棵树，会发生什么？最初这需要很长时间，但如果我们开始连续进行多次出队，那些未来的出队将明显更快，因为周围的树更少。

不过，这个设置有一个小问题。在正常的二项式堆中，树总是按顺序存储。如果我们只是不断地将新树放入我们的树集合中，随机合并它们，然后再添加更多树，则无法保证这些树会按任何顺序排列。因此，我们将需要一种新算法来将这些树合并在一起。

该算法背后的直觉如下。假设我们创建了一个从树顺序映射到树的哈希表。然后我们可以对数据结构中的每棵树执行以下操作：

查找并查看是否已经存在该顺序的树。

如果不是，则将当前树插入哈希表。

否则：将当前树与该顺序的树合并，从哈希表中删除旧树。递归地重复这个过程。

将当前树与该顺序的树合并，从哈希表中删除旧树。

递归地重复这个过程。

此操作确保当我们完成时，每个订单最多有一个树。它也相对有效。假设我们从 T 总树开始并以 t 总树结束。我们最终将进行的总合并次数将是 T - t - 1，每次我们进行合并都需要 O(1) 时间来完成。因此，此操作的运行时间将与树的数量（每棵树至少被访问一次）加上完成的合并次数成线性关系。

如果树的数量很少（比如 Θ(log n)），那么这个操作只需要 O(log n) 的时间。如果树的数量很大（例如 Θ(n)），则此操作将花费 Θ(n) 时间，但将只剩下 Θ(log n) 棵树，从而使未来的出队速度更快。

我们可以通过进行摊销分析和使用势函数来量化事情会变得多么好。设 Φ 为我们的势函数，设 Φ 为数据结构中树的数量。这意味着运营成本如下：

插入：O(1) 是否工作并将潜力增加一。摊销成本为 O(1)。

合并：O(1) 是否有效。一个堆的电位下降到 0，而另一个堆的电位增加了相应的量，因此电位没有净变化。因此，摊销成本为 O(1)。

Dequeue-Min：O(#trees + #merges) 是否有效并将潜力降低到 Θ(log n)，如果我们急切地将树合并在一起，我们将在二叉树中拥有的树的数量。我们可以用不同的方式来解释这一点。让我们将树的数量写为 Θ(log n) + E，其中 E 是树的“多余”数量。在这种情况下，完成的总功为 Θ(log n + E + #merges)。请注意，我们将对每个多余的树进行一次合并，因此完成的总工作量为 Θ(log n + E)。由于我们的潜力将树的数量从 Θ(log n) + E 下降到 Θ(log n)，所以潜力的下降是 -E。因此，dequeue-min 的摊销成本为 Θ(log n)。

另一种直观的方式来了解为什么 dequeue-min 的摊销成本是 Θ(log n) 是查看为什么我们有多余的树。这些额外的树在那里是因为那些该死的贪婪的插入物正在制造所有这些额外的树并且没有为它们付钱！因此，我们可以将与执行所有合并相关的成本“退回”到占用所有时间的单个插入，留下 Θ(log n)“核心”操作和我们将归咎于的一堆其他操作插入。

所以：

修改 3：在 dequeue-min 操作中，合并所有树以确保每个订单最多有一棵树。

此时，我们在 O(1) 时间内运行插入和合并，在摊销时间 O(log n) 内运行出列。这很漂亮！但是，我们仍然没有减少键工作。这将是具有挑战性的部分。

第二步：实现减键

现在，我们有一个“惰性二项式堆”而不是斐波那契堆。二项式堆和斐波那契堆之间的真正变化是我们如何实现减少键。

回想一下，减少键操作应该采用堆中已经存在的条目（通常，我们会有一个指向它的指针）和一个低于现有优先级的新优先级。然后它将该元素的优先级更改为新的较低优先级。

我们可以使用简单的算法非常快速地（在 O(log n) 时间内）实现此操作。获取应该减少其键的元素（可以在 O(1) 时间内定位；记住，我们假设我们有一个指向它的指针）并降低其优先级。然后，只要它的优先级低于其父节点，就反复将其与其父节点交换，当节点停止或到达树的根时停止。此操作需要时间 O(log n)，因为每棵树的高度最多为 O(log n)，并且每次比较需要时间 O(1)。

但请记住，我们正在努力做得比这更好——我们希望运行时为 O(1)！这是一个非常难以匹配的界限。我们不能使用任何将节点向上或向下移动树的过程，因为这些树的高度可以是 Ω(log n)。我们将不得不尝试更激烈的事情。

假设我们要减少一个节点的键。违反堆属性的唯一方法是节点的新优先级低于其父节点的优先级。如果我们查看以该特定节点为根的子树，它仍将遵循堆属性。所以这是一个完全疯狂的想法：如果每当我们减少一个节点的键时，我们切断到父节点的链接，然后把以该节点为根的整个子树带回到树的顶层呢？

修改4：让reduce-key减少一个节点的key，如果它的优先级小于它的父节点的优先级，则将它剪切并添加到根列表中。

这个操作会有什么效果？会发生几件事。

以前将我们的节点作为子节点的节点现在认为它的子节点数量错误。回想一下，n 阶二叉树被定义为有 n 个孩子，但这不再是真的了。根列表中的树集合会增加，增加未来出队操作的成本。我们堆中的树不一定是二叉树。它们可能是“以前的”二叉树，在不同的时间点失去了孩子。

数字（1）不是太大的问题。如果我们从其父节点中删除一个节点，我们可以将该节点的顺序减一，以表明它的子节点比它之前认为的要少。数字（2）也不是问题。我们可以将在下一个 dequeue-min 操作中完成的额外工作返还给 reduce-key 操作。

数字（3）是一个非常非常严重的问题，我们需要解决。这就是问题所在：二项式堆的效率部分源于这样一个事实，即任何 n 个节点的集合都可以存储在不同顺序的 Θ(log n) 树的集合中。原因是每棵二叉树都有 2n 个节点。如果我们可以开始从树中切割节点，那么我们就有可能拥有具有大量子节点（即高阶）但其中没有很多节点的树。例如，假设我们从一棵 k 阶树开始，然后对 k 的所有孙子执行减少键操作。这使得 k 成为一棵具有 k 阶的树，但它只包含 k + 1 个节点。如果我们到处重复这个过程，我们最终可能会得到一堆不同阶的树，其中只有很少的孩子。因此，当我们执行合并操作以将树组合在一起时，我们可能无法将树的数量减少到可管理的水平，从而打破了我们真的不想失去的 Θ(log n) 时间界限。

在这一点上，我们有点束缚。我们需要有很大的灵活性来调整树的形状，这样我们才能获得 O(1) 时间减少键的功能，但是我们不能让树任意地改变形状，否则我们最终会得到减少 -密钥的摊销运行时间增加到大于 O(log n) 的值。

所需的洞察力——老实说，我认为斐波那契堆中真正的天才——是两者之间的妥协。思路如下。如果我们从它的父节点切割一棵树，我们已经计划将父节点的等级降低一。当一个节点失去很多孩子时，问题就真正出现了，在这种情况下，它的排名会显着下降，而树中更高的节点却不知道它。因此，我们会说每个节点只允许失去一个孩子。如果一个节点丢失了第二个子节点，那么我们将从其父节点中删除该节点，这会将节点丢失的信息传播到树的更高层。

事实证明，这是一个很好的妥协。它允许我们在大多数情况下快速执行减少键（只要节点不是同一棵树的子节点），并且我们很少需要通过从其父节点切割节点来“传播”减少键，然后将该节点从其祖父节点中删除。

为了跟踪哪些节点丢失了孩子，我们将为每个节点分配一个“标记”位。每个节点最初都会清除标记位，但只要它失去一个子节点，它就会设置该位。如果在该位已设置后它丢失了第二个子节点，我们将清除该位，然后从其父节点中删除该节点。

修改5：为每个最初为假的节点分配一个标记位。当孩子从未标记的父级中删除时，标记父级。当孩子从标记的父级中删除时，取消标记父级并将父级从其父级中删除。

在 this CS Theory Stack Exchange question 和 this older Stack Overflow question 中，我草拟了一个证明，表明如果允许以这种方式修改树，那么任何 n 阶树必须至少包含 Θ(φⁿ) 个节点，其中 φ 是 golden ratio，约为 1.61。这意味着每棵树中的节点数量仍然是树的顺序的指数，尽管它比之前的指数更低。因此，我们之前对减少键操作的时间复杂度所做的分析仍然成立，尽管隐藏在 Θ(log n) 位中的项会有所不同。

最后一件事要考虑 - 减少键的复杂性如何？以前，它是 O(1)，因为我们只是切割以适当节点为根的树并将其移动到根列表。然而，现在我们可能不得不做一个“级联切割”，我们从它的父节点切割一个节点，然后从它的父节点切割那个节点，等等。这如何给 O(1) 时间减少键？

这里的观察是，我们可以为每个减少键操作添加一个“费用”，然后我们可以将其用于从其父节点中删除父节点。由于我们只在它已经失去两个孩子的情况下从它的父节点中删除一个节点，我们可以假设每个减少键操作都支付了削减其父节点所需的工作。当我们确实削减父级时，我们可以将这样做的成本记回早期的减少键操作之一。因此，即使任何单独的减少键操作可能需要很长时间才能完成，我们总是可以在早期调用中分摊工作，以便运行时分摊 O(1)。

第三步：链接列表比比皆是！

最后还有一个细节我们要谈。到目前为止，我描述的数据结构很棘手，但它似乎并不复杂。斐波那契堆以可怕着称……这是为什么呢？

原因是为了实现上述所有操作，需要以非常巧妙的方式实现树结构。

通常，您可以通过让每个父节点向下指向所有子节点（可能通过一组子节点）或 using the left-child/right-sibling representation 来表示多路树，其中父节点有一个指向一个子节点的指针，而子节点又指向其他孩子的名单。对于二项式堆，这是完美的。我们需要对树进行的主要操作是连接操作，其中我们使一个根节点成为另一个根节点的子节点，因此将树中的指针从父节点指向子节点是完全合理的。

斐波那契堆中的问题是这种表示在考虑减少键步骤时效率低下。斐波那契堆需要支持标准二项式堆的所有基本指针操作以及从父级中删除单个子级的能力。

考虑多路树的标准表示。如果我们通过让每个父节点存储一个数组或指向其子节点的指针列表来表示树，那么我们不能有效地（在 O(1) 中）从子节点列表中删除一个子节点。换句话说，减少键的运行时间将由删除子节点的簿记步骤而不是将子树移动到根列表的逻辑步骤支配！同样的问题也出现在左子右兄弟的表示中。

这个问题的解决方案是以一种奇怪的方式存储树。每个父节点存储一个指向其单个（和任意）子节点的指针。然后，孩子们被存储在一个循环链表中，每个孩子都指向它的父母。由于可以在 O(1) 时间内连接两个循环链表，并在 O(1) 时间内从其中插入或删除单个条目，因此可以有效地支持必要的树操作：

使一棵树成为另一棵树的子树：如果第一棵树没有子树，则将其子指针设置为指向第二棵树。否则，将第二棵树拼接到第一棵树的循环链接子列表中。

从树中移除一个子节点：将该子节点从父节点的子节点链表中拼接出来。如果它是选择代表父节点的子节点的单个节点，则选择一个兄弟节点来替换它（如果它是最后一个子节点，则将指针设置为 null。）

由于可能出现的不同边缘情况的数量，在执行所有这些操作时需要考虑和检查的情况非常多。与所有指针杂耍相关的开销是斐波那契堆在实践中比它们的渐近复杂性可能暗示的慢的原因之一（另一个大的原因是删除最小值的逻辑，这需要辅助数据结构）。

修改 6：使用树的自定义表示，支持高效连接树木和从另一棵树中切割一棵树。

结论

我希望这个答案能够阐明斐波那契堆的奥秘。我希望您可以通过基于合理见解的一系列简单步骤，看到从更简单的结构（二项式堆）到更复杂的结构的逻辑进展。以删除为代价来使插入具有摊销效率并不是不合理的，通过删除子树来实现减少键同样也不是太疯狂。从那里开始，其余的细节是确保结构仍然有效，但它们更多的是其他部分的后果而不是原因。

如果您有兴趣了解有关斐波那契堆的更多信息，您可能需要查看这个由两部分组成的系列讲座幻灯片。 Part one 介绍了二项式堆并展示了惰性二项式堆的工作原理。 Part two 探索斐波那契堆。这些幻灯片比我在这里介绍的更深入。

希望这可以帮助！

---