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

Question

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

data-structuresfibonacci-heap

66

我已经阅读了Fibonacci堆的维基百科文章并阅读了CLRS对数据结构的描述，但它们很少提供有关为什么这种数据结构有效的直觉。 Fibonacci堆为什么被设计成这样？它们是如何工作的？

谢谢！

- templatetypedef

2

CLRS这本书并不是一个好的直觉来源。如果你在那里一直找不到直觉，我建议使用Robert Lafore的《数据结构与算法》。这本书是洞察力的宝库！ - user5193682

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- templatetypedef · Accepted Answer

本答案将会比较长，但我希望它能够提供一些关于斐波那契堆的来源的见解。我假设你已经熟悉二项堆和摊还分析。

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

在深入了解斐波那契堆之前，探讨为什么我们需要它可能是一个不错的选择。有很多其他类型的堆（例如二叉堆和二项堆），那我们为什么需要另外一个堆呢？

主要原因出现在Dijkstra算法和Prim算法中。这两个图算法都通过维护一个包含与节点相关联的优先级的优先队列来工作。有趣的是，这些算法依赖于一个叫做decrease-key的堆操作，它接受已经在优先队列中的条目，然后降低其键（即提高其优先级）。事实上，这些算法的运行时间很大程度上取决于你需要调用 decrease-key 的次数。如果我们能够构建一个优化 decrease-key 的数据结构，我们就可以优化这些算法的性能。在二叉堆和二项式堆的情况下，decrease-key 的时间复杂度为 O(log n)，其中 n 是优先队列中节点的数量。如果我们能将其降至 O(1)，那么 Dijkstra算法和Prim算法的时间复杂度将从 O(m log n) 降至 (m + n log n)，这比以前更快。因此，尝试构建一个有效支持 decrease-key 的数据结构是有意义的。

考虑设计更好的堆结构还有另一个原因。当向空二叉堆添加元素时，每次插入需要O(log n)的时间。如果我们事先知道所有n个元素，则可以在O(n)的时间内构建二叉堆，但如果元素以流的形式到达，则不可能这样做。对于二项堆，在连续插入n个元素时，每个插入的平摊时间为O(1)，但如果插入与删除交替进行，则插入可能需要Ω(log n)的时间。因此，我们可能希望搜索优化插入时间为O(1)的优先队列实现。

第一步：延迟二项堆

为了开始构建斐波那契堆，我们将从二项堆开始，并修改它以尝试使插入时间为O(1)。尝试这样做并不是完全不合理的-毕竟，如果我们要执行大量插入而不是许多出队操作，则优化插入是有意义的。

如果您还记得，二项堆是通过将堆中的所有元素存储在一组二项树中来工作的。一个n阶二项树有2ⁿ个节点，并且堆被构造成遵守堆属性的一组二项树。通常，二项堆中的插入算法如下所示：

创建一个新的独立节点（这是一个0阶树）。
如果有一个0阶树：
- 将两个0阶树合并为一个1阶树。
- 如果有一个1阶树：
  - 将两个1阶树合并为一个2阶树。
  - 如果有一个2阶树：
    - ...

这个过程确保每个时间点都最多有一个树的每个顺序。由于每棵树比它的顺序多指数级的节点，这保证了总树数很小，从而让dequeues快速运行(因为我们在执行dequeue-min步骤后不必查看太多不同的树)。

然而，这也意味着将节点插入二项堆的最坏运行时间为Θ(log n)，因为我们可能有Θ(log n)个需要合并在一起的树。这些树之所以需要合并在一起，仅仅是因为在执行去队列步骤时需要保持树的数量较少，在未来的插入操作中保持树的数量较少没有任何好处。

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

修改1：将节点插入堆时，只需创建一个顺序为0的树，并将其添加到现有的树集合中。不要合并树。

我们可以进行另一种改变。通常情况下，当我们合并两个二项堆时，我们会执行一个合并步骤，以一种确保结果树中每个阶数最多只有一棵树的方式将它们组合在一起。同样，我们进行这种压缩是为了使出队操作更快，并且合并操作没有必要为此付出代价。因此，我们将进行第二次改变：

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

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

如果我们的插入操作只是增加了更多的树，那么我们执行的第一个出队操作肯定需要 Ω(n) 的时间。但这并不意味着每个出队操作都必须很耗费时间。如果我们在执行完一个出队操作后将堆中的所有树合并在一起，使得最终只剩下每个阶次的一棵树，会怎样呢？初始时需要花费大量时间，但如果我们连续进行多个出队操作，那么未来的出队操作就会显著加快，因为此时堆中没有那么多树。

然而，这种设置还有一个小问题。在一个普通的二项堆中，树总是按照顺序储存的。如果我们只是简单地把新树扔进集合中，随机地合并它们，并在此之后添加更多树，就不能保证树的顺序。因此，我们需要一个新的算法来合并这些树。

该算法的思路如下。假设我们创建一个哈希表将树的阶次（order）映射到树上。然后，我们可以对数据结构中的每一棵树执行以下操作：

查找是否已有该顺序的树。
如果没有，将当前树插入哈希表中。
否则:
- 将当前树与该顺序的树合并，从哈希表中删除旧树。
- 递归重复此过程。

此操作确保完成后，每个顺序最多只有一棵树。它也相对高效。假设我们开始有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)。
出队最小值：O(#trees + #merges)的工作量，并将潜力降至Θ(log n)，即如果我们急切地将树合并在一起，我们将在二项树中拥有的树的数量。我们可以用不同的方式解决这个问题。让树的数量被写成Θ(log n)+E，其中E是“过剩”的树的数量。在这种情况下，总共的工作量是Θ(log n + E + #merges)。请注意，我们每多一个过剩的树就会做一次合并，因此总共的工作量是Θ(log n + E)。由于我们的潜力将树的数量从Θ(log n) + E降至Θ(log n)，因此潜力的下降为-E。因此，出队最小值的平摊成本为Θ(log n)。

另一种直观理解出队最小值的摊销成本为Θ(log n)的方法是看看为什么我们有剩余树。这些额外的树存在是因为那些可恶的贪婪插入操作制造了所有这些额外的树而没有为它们付费！因此，我们可以将与执行所有合并相关的成本反向收取到占用所有时间的各个插入操作中，留下Θ(log n) "核心" 操作和一堆其他操作，我们将归咎于插入操作。

因此：

修改3：在出队最小值操作中，整合所有树，以确保每个阶数最多只有一个树。

此时，我们具有O(1)时间运行的插入和合并，以及摊销时间为O(log n)的出队操作。这很棒！然而，我们还没有使降低关键字起作用。那将是具有挑战性的部分。

第二步：实现降低关键字

现在，我们拥有一个"懒惰的二项式堆"而不是斐波那契堆。二项式堆和斐波那契堆之间的真正变化在于我们如何实现降低关键字。

请回忆一下，减少键值操作应该针对堆中已有的条目(通常我们会有一个指针指向它)和一个比现有优先级低的新优先级。然后，它将该元素的优先级更改为新的较低优先级。

我们可以使用简单的算法非常快地实现这个操作(时间复杂度为O(log n))。找到要降低键值的元素(可以在O(1)时间内定位；记住，我们假设我们有一个指针指向它)，并降低它的优先级。然后，只要其优先级低于其父节点，就重复地将其与其父节点交换，停止条件是节点静止或达到树的根。这个操作的时间复杂度为O(log n)，因为每棵树的高度至多为O(log n)，每次比较的时间复杂度为O(1)。

但要记住，我们想做得比这还要好——我们希望运行时间为O(1)! 这是一个非常严格的限制。我们不能使用任何会将节点上移或下移的过程，因为这些树的高度可以是Ω(log n)。我们必须尝试一些更激烈的方法。

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

“修改4”：使减少键减少节点的键，并且如果其优先级小于其父项的优先级，则将其剪切并添加到根列表中。

这个操作的效果是什么？会发生几件事情：

1. 先前将我们的节点作为子节点的节点现在认为它们有错误数量的子节点。回想一下，阶数为n的二项树被定义为具有n个孩子，但不再是真的。 2. 根列表中的树集合将上升，增加未来出列操作的成本。 3. 我们堆中的树不一定再是二项式树了。它们可能是在不同时间点失去孩子的“曾经”的二项式树。

数字（1）并不是太大的问题。如果我们从父节点中剪掉一个节点，我们只需将该节点的顺序减一，以表明它比先前认为的孩子数少。数字（2）也不是问题。我们只需将下一个dequeue-min操作中额外完成的工作退还给decrease-key操作。

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

在这一点上，我们有些困境。我们需要在树的重塑方面具有很大的灵活性，以便能够获得O(1)时间的减少键功能，但我们不能让树随意重塑，否则我们的减少键的摊销运行时间将增加到大于O(log n)的某个值。

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

事实证明，这是一个很好的妥协。它让我们在大多数情况下快速地进行减少键操作（只要节点不是同一棵树的子节点），而只有在很少的情况下我们才需要通过从其父节点中割下一个节点，然后再从其祖父节点中割下该节点来“传播”减少键。

为了追踪哪些节点失去了子节点，我们将为每个节点分配一个“标记”位。每个节点最初都没有设置标记位，但是每当它失去一个子节点时，就会设置该位。如果在已经设置了标记位之后再次失去一个子节点，我们将清除该位，然后将该节点从其父节点中删除。

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

在这个 CS Theory Stack Exchange 问题和这个旧的 Stack Overflow 问题中，我概述了一个证明，表明如果允许修改树，则任何n阶树都必须包含至少Θ(φⁿ)个节点，其中φ是黄金比例，约为1.61。这意味着每棵树中的节点数仍然是树的阶数的指数级别，尽管它的指数比之前低。因此，我们之前对于减小键操作的时间复杂度的分析仍然成立，尽管隐藏在Θ(log n)位中的项将不同。

有一件非常重要的事情需要考虑 - decrease-key 的复杂度如何？以前，它是O(1)，因为我们只是剪切了适当节点的树并将其移动到根列表中。然而，现在我们可能不得不进行“级联剪切”，即从其父节点剪切一个节点，然后从其父节点剪切该节点，以此类推。那么这如何使 decrease-keys 的时间复杂度为 O(1) 呢？

观察到，我们可以为每个 decrease-key 操作添加一个“费用”，然后用它来剪切父节点。由于我们仅在一个节点已经失去两个子节点时才从其父节点剪切一个节点，因此我们可以假装每个 decrease-key 操作支付必要的工作量来剪切其父节点。当我们确实剪切父节点时，我们可以将其成本退回到较早的 decrease-key 操作之一。因此，尽管任何单个 decrease-key 操作可能需要很长时间才能完成，但我们始终可以将工作分摊到先前的调用中，使运行时间为平均 O(1)。

第三步：链表无处不在！

我们还需要谈论一个最终的细节。到目前为止，我描述的数据结构很棘手，但似乎并不是灾难性地复杂。斐波那契堆以令人生畏的声誉而闻名……为什么呢？

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

通常，你可以通过让每个父节点指向所有子节点（可能通过具有子节点数组）或通过使用左孩子/右兄弟表示法来表示多路树。对于二项堆，这是完美的。我们需要在树上执行的主要操作是连接操作，在其中我们使一个根节点成为另一个根节点的子节点，因此从父节点到子节点的指针是完全合理的。

在斐波那契堆中的问题在于，当考虑减少键步骤时，这种表示方法效率低下。斐波那契堆需要支持标准二项堆的所有基本指针操作和从父节点剪切单个子节点的能力。

考虑多路树的标准表示形式。如果我们通过让每个父节点存储一个指向其子节点数组或列表的指针来表示树，则无法在O(1)时间内有效地从子节点列表中删除子节点。换句话说，降低键值的运行时间将被删除子节点的簿记步骤所支配，而不是将子树移动到根列表的逻辑步骤！左子节点、右兄弟表示法中也存在相同的问题。

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

将一个树作为另一个树的子节点：如果第一棵树没有子节点，则将其子指针设置为指向第二棵树。否则，将第二棵树插入到第一棵树的循环链接子列表中。
从树中删除一个子节点：将该子节点从其父节点的子节点链表中拼接出来。如果它是代表父节点子节点的唯一节点，则选择其中一个兄弟节点替换它（或者如果它是最后一个子节点，则将指针设置为空）。

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

修改6：使用支持树的高效合并和剪切的自定义表示。

结论

我希望这个答案能解开斐波那契堆的神秘面纱。我希望你能看到从一个更简单的结构（二项堆）到一个更复杂的结构的逻辑进展，通过一系列基于合理洞察力的简单步骤。想要通过分摊代价使插入操作高效而牺牲删除操作并不是不合理的，同样地，通过剪切子树来实现降低键值也不是太疯狂。从那里开始，结构仍然有效的其余细节是确保结构仍然有效，但它们更多地是其他部分的结果，而不是原因。

如果你对学习更多关于斐波那契堆的知识感兴趣，你可以查看这个两部分系列讲义。第一部分介绍了二项堆，并展示了懒惰二项堆的工作方式。第二部分探讨了斐波那契堆。这些讲义比我在这里介绍的内容更深入数学。