斐波纳契堆数据结构背后的直觉是什么？ [英] What is the intuition behind the Fibonacci heap data structure?

问题描述

我已经阅读了关于斐波那契堆的维基百科文章，并阅读了CLRS对数据结构的描述，但它们提供了一点直觉为什么这个数据结构工作。为什么斐波纳契堆的设计方式是他们的？他们如何工作？

谢谢！

解决方案

将会很长，但我希望它有助于提供一些关于斐波纳契堆来自哪里的洞察力。我将假设您已经熟悉二项式堆和摊销分析。

动机：为什么斐波纳契堆积？ h1>

在跳入斐波纳契堆之前，首先要了解为什么我们甚至需要它们，这可能是很好的。有很多其他类型的堆（二进制堆和二项式堆，那么为什么我们需要另外一个？

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

另外还有一个原因可以考虑设计一个更好的堆结构。向空二进制堆添加元素时，每次插入都需要时间O（log n）。可以构建二进制堆时间O（n），如果我们提前知道所有的n个元素，但是如果元素到达流，这是不可能的。在二项式堆的情况下，插入n个连续的元素分别获得摊销时间O（1），但是如果插入与删除交错，那么插入可能会以每个欧姆（log n）的时间结束。因此，我们可能要搜索优化插入的优先级队列实现，以便花费时间O（1）。

第一步：懒惰二项式堆

要开始构建斐波纳契堆，我们将从二叉树开始，并修改它，尝试使插入花费时间O（1）。尝试这一切并不是所有这些 - 毕竟，如果我们要做大量的插入，而不是很多的出列，那么优化插入是有意义的。

如果你记得，二项式堆工作，通过将堆中的所有元素存储在二叉树。阶n的二叉树在其中有2个 ⁿ 个节点，堆是作为二叉树的集合的结构，它们都遵循堆属性。通常，二项式堆中的插入算法工作如下：

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


• 如果有一棵订单树0：
  
  
  
  
  • 将0的两棵树合并成一棵树订单1。
  
  
  • 如果有一个订单树1：
    
    
    
    
    • 将1号的两棵树合并到一起树状订单2。
    
    
    • 如果有一棵订单树2：
    
    
    • ...
    
    
  
  

此过程确保在每个时间点至多有每个订单的一棵树。由于每个树比其顺序保持指数多的节点，这样可以保证树的总数很小，从而使得出队快速运行（因为在进行出队最小步骤之后我们不需要看太多不同的树）。

但是，这也意味着将节点插入到二项式堆中的最坏情况是&Theta（log n），因为我们可能会有&（log n）需要合并的树木。这些树需要合并在一起，因为我们需要在进行出队步骤时保持树木的数量低，今后插入树木的数量绝对没有任何好处。

这将引入第二个二项式堆的偏离：

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

我们可以做另一个改变。通常，当我们将两个二项式堆合并在一起时，我们将合并步骤将它们组合在一起，以确保生成的树中每个顺序最多有一棵树。再次，我们做这个压缩，使得出队是快速的，没有真正的理由为什么合并操作应该为此支付。因此，我们将进行第二个更改：

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

如果我们进行这种更改，我们很容易在我们的排队操作上获得O（1）因为我们正在做的是创建一个新节点并将其添加到树的集合中。但是，如果我们只是进行这种改变，而不做任何事情，我们就完全打破了出队最小运行的性能。回想一下，去除最小值后，dequeue-min需要扫描堆中所有树的根，以便找到最小的值。如果我们通过插入他们的方式添加&Theta（n）节点，我们的出队操作将不得不花费&（。）时间查看所有这些树。这是一个巨大的表现命中...我们可以避免吗？

如果我们的插入真的只是添加更多的树，那么我们做的第一个出队肯定会采用Ω（n ） 时间。然而，这并不意味着每个出队必须是昂贵的。如果在进行出队之后，我们将堆中的所有树结合在一起，这样我们最终只能得到每个订单的一棵树？这将需要很长时间，但如果我们开始多次出现队列，那么未来出现的队列将会明显更快，因为树木周围环境较少。

虽然这个设置有点问题，在正常的二叉树堆中，树总是按顺序存储。如果我们只是继续在我们的树丛中投掷新的树木，随机聚结它们，再加上更多的树木，就不能保证树木的顺序。因此，我们将需要一种新的算法将这些树合并在一起。

这个算法背后的直觉如下。假设我们创建一个从树形订单映射到树的散列表。然后，我们可以对数据结构中的每个树进行以下操作：

• 查看是否已经有该树的树。


• 如果没有，请将当前树插入哈希表。


• 否则：
  
  
  
  
  • 将当前树与该订单的树合并，从
    哈希表中删除旧树。
  
  
  • 递归地重复此过程。
  
  

此操作确保完成后，每个订单最多只有一棵树。这也比较有效率。假设我们从T总树开始，最后总共t树。我们最终完成的合并次数将为T - t - 1，每当我们合并时，O（1）都需要时间。因此，此操作的运行时间将是树的数量（每棵树至少访问一次）加上完成的合并次数。

如果数量树很小（说，Θ（log n）），那么这个操作只需要时间O（log n）。如果树的数量很大（例如，Θ（n）），那么这个操作将需要&（;）的时间，但是只会留下剩下的树，剩下的树（log n），使得未来出现得更快。 p>

我们可以通过进行摊销分析和使用潜在功能来量化更好的事情。让&Phi成为我们的潜在功能，让&Phi是数据结构中的树数。这意味着操作的成本如下：

• 插入：O（1）是否工作，增加一个潜力。摊销成本为O（1）。


• 合并：O（1）是否正常工作。一堆的潜力下降到0，另一堆的潜力增加了相应的数量，所以潜在的潜力没有变化。因此，摊销成本为O（1）。


• 出队 - 最小：O（#trees + #merges）是否可以下降到Theta （log n），如果我们热切地将树合并在一起，我们将在二叉树中拥有树数。我们可以用不同的方式解释这个问题。我们把树的数量写成Θ（log n）+ E，其中E是树的数量。在这种情况下，完成的工作是&（log n + E + #merges）。请注意，我们将对每个多余的树进行一次合并，因此完成的总计是&Theta（（log n + E））。由于我们的潜力将来自The Theta的树木数量（log n）+ E降低到&Theta（log n），潜在的下降是-E。因此，dequeue-min的摊销成本为&（log n）。

另一种直观的方法来看看为什么摊还成本一个dequeue-min是Θ（log n）是通过查看为什么我们有剩余的树。这些额外的树木在那里，因为那些贪婪的插件正在使所有这些额外的树木，而不是为他们付钱！因此，我们可以将与所有合并相关的成本收回到所有时间的个人插入中，留下The（日志）核心操作和一系列我们将会责怪的其他操作

因此：

修改3 ：在出队最小操作中，合并所有树，以确保每个订单最多只有一棵树。

此时，我们在时间O（1）中插入和合并运行，并且以摊余时间O（log n）运行的出库。这很漂亮！但是，我们还没有减少关键工作。这将是一个具有挑战性的部分。

第二步：实现减少密钥

现在，我们有一个懒惰的二项式堆而不是斐波那契堆。二进制堆和斐波那契堆之间的真正变化是我们如何实现减少密钥。

回想一下，reduce-key操作应该在堆中已经有一个条目通常我们会有一个指针）和一个低于现有优先级的新优先级。然后将该元素的优先级更改为新的较低优先级。

我们可以使用简单的算法快速（在时间O（log n））中实现此操作。取其键值要减少的元素（可以在O（1）时间内）;记住，我们假设我们有一个指针），并降低其优先级。然后，只要其优先级低于其父节点，就重复与其父节点进行交换，当节点到达休眠或到达树根的时候停止。这个操作需要时间O（log n），因为每棵树的高度最多为O（log n），每个比较需要时间O（1）。

我们想要做的比这更好 - 我们希望运行时是O（1）！这是一个很难匹配的 。我们不能使用将节点向上或向下移动到树上的任何进程，因为这些树具有可以是&Omega（log n）的高度。我们必须尝试更多的东西。

假设我们要减少一个节点的密钥。将会违反heap属性的唯一方法是如果节点的新优先级低于其父级别的优先级。如果我们看着那个特定节点上的子树，它仍然会遵循heap属性。所以这里是一个完全疯狂的想法：如果每当我们减少一个节点的密钥时，我们剪切到父节点的链接，然后将整个子树植根于该节点的顶层。

修改4 ：减少键降低节点的密钥，如果优先级小于其父级的优先级，剪切并将其添加到根列表中。

此操作的效果是什么？

1. 以前有我们的节点作为孩子的节点现在认为它的孩子数量错误。回想一下，订单n的二项式树被定义为有n个子代，但这不再是真的。


2. 根列表中的树的集合将会上升，增加未来的成本出库作业。


3. 我们堆中的树不一定再次是二叉树。他们可能是以前的二项式树，它们在不同时间点失去了孩子。

数字（1）不是太多一个问题。如果我们从一个父节点切割一个节点，我们可以将该节点的顺序减少一个，以表明它的节点数少于之前所做的。数（2）也不是问题。我们可以将下一个出队最小操作中的额外工作退还给减号操作。

数字（3）是一个非常非常严重的问题，我们将需要解决。这里的问题是：二项式堆的效率部分源于以下事实：n个节点的任何集合都可以存储在不同顺序的&（log n）树的集合中。这样做的原因是每个二叉树都有2个 ⁿ 节点。如果我们可以从树中切出节点，那么我们冒着拥有大量子树（即高阶）但是没有很多节点的树的风险。例如，假设我们从一个顺序为k的树开始，然后在k的所有孙子上执行减号操作。这使得k成为一个具有秩k的树，但是它只包含k + 1个总节点。如果我们继续重复这个过程，我们可能会得到一堆各种各样的订单，其中有很少的孩子。因此，当我们进行合并操作来将树组合在一起时，我们可能不会将树木数量减少到可管理的水平，打破了我们真正不想失去的Theta（日志） - 时间限制。 p>

在这一点上，我们有点绑定。我们需要有很多的灵活性，如何重构树，以便我们可以获得O（1）时间的减少关键功能，但是我们不能让树被任意重塑，或者我们最终会减少 - 钥匙的摊销运行时间增加到大于O（log n）的东西。

需要的洞察力 - 坦白说，我认为是斐波那契堆的真正天才 - 是两者之间的妥协。想法如下。如果我们从父母中删除一棵树，我们已经在计划将父节点的排名降低一个。当一个节点失去一个孩子的时候，这个问题真的出现了，在这种情况下，它的等级明显下降，而树中的任何节点都没有更高的知识。因此，我们将说每个节点只允许丢失一个孩子。如果一个节点丢失了第二个子节点，那么我们将从该父节点中删除该节点，从而传播节点在树中缺少的信息。

这是一个很大的妥协。它允许我们在大多数情况下快速减少键（只要节点不是同一棵树的子节点），并且很少我们必须通过从其父节点切割节点来传播减号，然后从其祖父母中切断节点。

为了跟踪哪些节点丢失了孩子，我们将为每个节点分配一个标记位。每个节点将初始化标记位清零，但是当它丢失一个小孩时，它将被置位。如果在该位已经被设置之后丢失了第二个孩子，我们将清除该位，然后从该父节点中删除节点。

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

在 这个较旧的Stack Overflow问题 ，我' ve绘制了一个证明，表明如果树被允许以这种方式被修改，那么任何n阶树必须至少包含&Theta（φ ⁿ ）个节点，其中φ是黄金比例，约为1.61。这意味着每个树中的节点数量仍然是树的顺序的指数，尽管它是从之前的较低的指数。因此，我们之前关于减少关键操作的时间复杂度的分析仍然存在，尽管隐藏在&Theta（log n）位中的术语将是不同的。

有一件最后一件事要考虑 - 减号的复杂度如何？以前，这是O（1），因为我们只是剪切根据适当节点的树并将其移动到根列表。然而，现在我们可能需要做一个级联切割，其中我们从其父节点中切下一个节点，然后从 父节点中切下节点。那么给出O（1）个时间减少键？

这里的观察是，我们可以为每个减少键操作添加一个费用，然后我们可以花费从其父级切断父节点。由于我们只有在已经丢失了两个子节点的情况下，才从父节点中删除一个节点，所以我们可以假设每个减号操作支付切割父节点所需的工作。当我们切断父母时，我们可以将这样做的成本收回到早期的减少关键业务之一。因此，即使任何单个减少关键操作可能需要很长时间来完成，我们可以随时在早期调用中摊销工作，以便运行时间摊销O（1）。

第三步：链接列表！

有一个最后的细节我们必须谈谈。到目前为止，我所描述的数据结构是棘手的，但似乎并不奇怪。斐波那契堆有可怕的声誉为什么呢？为什么呢？

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

通常，您可以通过让每个父点指向所有的孩子（可能通过拥有一个孩子数组） ）或者通过使用左儿/右兄弟表示，父母有一个指向一个孩子的指针，而指向另一个孩子的列表。对于二项式堆，这是完美的。我们需要在树上执行的主要操作是一个加入操作，其中我们使一个根节点成为另一个根节点，所以从父母到子节点的树中的指针是完全合理的。

斐波那契堆中的问题是，考虑减少关键步骤时，该表示效率低下。斐波那契堆需要支持标准二项式堆的所有基本指针操作，并且可以从父母中切割单个孩子。

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

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

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




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

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

修改6 ：使用树的自定义表示形式支持树的有效连接并从另一个树切割一棵树。

结论

我希望这个答案揭示了这个神秘面纱是斐波纳契堆。我希望通过基于合理的见解的一系列简单的步骤，您可以看到从更简单的结构（二项式堆）到更复杂结构的逻辑进展。想要以插入费用为代价，以牺牲损失为代价来进行插入是不合理的，通过删除子树来实现减号也不是太疯狂。从那里，其余的细节是确保结构仍然有效，但它们更多的是其他部分的后果，而不是原因。

如果您有兴趣了解有关斐波纳契堆积的信息，您可能需要查看这两部分的讲座幻灯片。 第一部分介绍二项式堆并显示如何懒惰的二项式堆工作。 第二部分探讨斐波那契堆。这些幻灯片比我在这里介绍的更深入数学深度。

希望这有帮助！

I've read the Wikipedia article on Fibonacci heaps and read CLRS's description of the data structure, but they provide little intuition for why this data structure works. Why are Fibonacci heaps designed the way they are? How do they work?

Thanks!

解决方案

This answer is going to be pretty long, but I hope it helps provide some insight as to where the Fibonacci heap comes from. I'm going to assume that you're already familiar with binomial heaps and amortized analysis.

Motivation: Why Fibonacci Heaps?

Before jumping into Fibonacci heaps, it's probably good to explore why we even need them in the first place. There are plenty of other types of heaps (binary heaps and binomial heaps, for example), so why do we need another one?

The main reason comes up in Dijkstra's algorithm and Prim's algorithm. Both of these graph algorithms work by maintaining a priority queue holding nodes with associated priorities. Interestingly, these algorithms rely on a heap operation called decrease-key that takes an entry already in the priority queue and then decreases its key (i.e. increases its priority). In fact, a lot of the runtime of these algorithms is explained by the number of times you have to call decrease-key. If we could build a data structure that optimized decrease-key, we could optimize the performance of these algorithms. In the case of the binary heap and binomial heap, decrease-key takes time O(log n), where n is the number of nodes in the priority queue. If we could drop that to O(1), then the time complexities of Dijkstra's algorithm and Prim's algorithm would drop from O(m log n) to (m + n log n), which is asymptotically faster than before. Therefore, it makes sense to try to build a data structure that supports decrease-key efficiently.

There is another reason to consider designing a better heap structure. When adding elements to an empty binary heap, each insertion takes time O(log n). It's possible to build a binary heap in time O(n) if we know all n elements in advance, but if the elements arrive in a stream this isn't possible. In the case of the binomial heap, inserting n consecutive elements takes amortized time O(1) each, but if insertions are interlaced with deletions, the insertions may end up taking Ω(log n) time each. Therefore, we might want to search for a priority queue implementation that optimizes insertions to take time O(1) each.

Step One: Lazy Binomial Heaps

To start off building the Fibonacci heap, we're going to begin with a binomial heap and modify it try to make insertions take time O(1). It's not all that unreasonable to try this out - after all, if we're going to do a lot of insertions and not as many dequeues, it makes sense to optimize insertions.

If you'll recall, binomial heaps work by storing all of the elements in the heap in a collection of binomial trees. A binomial tree of order n has 2ⁿ nodes in it, and the heap is structures as a collection of binomial trees that all obey the heap property. Typically, the insertion algorithm in a binomial heap work as follows:

• Create a new singleton node (this is a tree of order 0).
• If there is a tree of order 0:
  • Merge the two trees of order 0 together into a tree of order 1.
  • If there is a tree of order 1:
    • Merge the two trees of order 1 together into a tree order 2.
    • If there is a tree of order 2:
    • ...

This process ensures that at each point in time, there is at most one tree of each order. Since each tree holds exponentially more nodes than its order, this guarantees that the total number of trees is small, which lets dequeues run quickly (because we don't have to look at too many different trees after doing a dequeue-min step).

However, this also means that the worst-case runtime of inserting a node into a binomial heap is Θ(log n), because we might have Θ(log n) trees that need to get merged together. Those trees need to be merged together only because we need to keep the number of trees low when doing a dequeue step, and there's absolutely no benefit in future insertions to keeping the number of trees low.

This introduces the first departure from binomial heaps:

Modification 1: When inserting a node into the heap, just create a tree of order 0 and add it to the existing collection of trees. Do not consolidate trees together.

There is another change we can make. Normally, when we merge together two binomial heaps, we do a merge step to combine them together in a way that ensures that there is at most one tree of each order in the resulting tree. Again, we do this compression so that dequeues are fast, and there's no real reason why the merge operation ought to have to pay for this. Therefore, we'll make a second change:

Modification 2: When merging two heaps together, just combine all their trees together without doing any merging. Do not consolidate any trees together.

If we make this change, we pretty easily get O(1) performace on our enqueue operations, since all we're doing is creating a new node and adding it to the collection of trees. However, if we just make this change and don't do anything else, we completely break the performance of the dequeue-min operation. Recall that dequeue-min needs to scan across the roots of all the trees in the heap after removing the minimum value so that it can find the smallest value. If we add in Θ(n) nodes by inserting them in the way, our dequeue operation will then have to spend Θ(n) time looking over all of these trees. That's a huge performance hit... can we avoid it?

If our insertions really just add more trees, then the first dequeue we do will certainly take Ω(n) time. However, that doesn't mean that every dequeue has to be expensive. What happens if, after doing a dequeue, we coalesce all the trees in the heap together such that we end up with only one tree of each order? This will take a long time initially, but if we start doing multiple dequeues in succession, those future dequeues will be significantly faster because there are fewer trees lying around.

There's a slight problem with this setup, though. In a normal binomial heap, the trees are always stored in order. If we just keep throwing new trees into our collection of trees, coalescing them at random times, and adding even more trees after that, there's no guarantee that the trees will be in any order. Therefore, we're going to need a new algorithm to merge those trees together.

The intuition behind this algorithm is the following. Suppose we create a hash table that maps from tree orders to trees. We could then do the following operation for each tree in the data structure:

• Look up and see if there's already a tree of that order.
• If not, insert the current tree into the hash table.
• Otherwise:
  • Merge the current tree with the tree of that order, removing the old tree from the hash table.
  • Recursively repeat this process.

This operation ensures that when we're done, there's at most one tree of each order. It's also relatively efficient. Suppose that we start with T total trees and end up with t total trees. The number of total merges we'll end up doing will be T - t - 1, and each time we do a merge it will take time O(1) to do it. Therefore, the runtime for this operation will be linear in the number of trees (each tree is visited at least once) plus the number of merges done.

If the number of trees is small (say, Θ(log n)), then this operation will only take time O(log n). If the number of trees is large (say, Θ(n)), then this operation will take Θ(n) time, but will leave only Θ(log n) trees remaining, making future dequeues much faster.

We can quantify just how much better things will get by doing an amortized analysis and using a potential function. Let Φ to be our potential function and let Φ be the number of trees in the data structure. This means that the costs of the operations are as follows:

• Insert: Does O(1) work and increases the potential by one. Amortized cost is O(1).
• Merge: Does O(1) work. The potential of one heap is dropped to 0 and the other heap's potential is increased by a corresponding amount, so there is no net change in potential. The amortized cost is thus O(1).
• Dequeue-Min: Does O(#trees + #merges) work and decreases the potential down to Θ(log n), the number of trees we'd have in the binomial tree if we were eagerly merging the trees together. We can account for this in a different way. Let's have the number of trees be written as Θ(log n) + E, where E is the "excess" number of trees. In that case, the total work done is Θ(log n + E + #merges). Notice that we'll do one merge per excess tree, and so the total work done is Θ(log n + E). Since our potential drops the number of trees from Θ(log n) + E down to Θ(log n), the drop in potential is -E. Therefore, the amortized cost of a dequeue-min is Θ(log n).

Another intuitive way to see why the amortized cost of a dequeue-min is Θ(log n) is by looking at why we have surplus trees. These extra trees are there because those darned greedy inserts are making all these extra trees and not paying for them! We can therefore "backcharge" the cost associated with doing all the merges back to the individual insertions that took up all that time, leaving behind the Θ(log n) "core" operation and a bunch of other operations that we'll blame on the insertions.

Therefore:

Modification 3: On a dequeue-min operation, consolidate all trees to ensure there's at most one tree of each order.

At this point, we have insert and merge running in time O(1) and dequeues running in amortized time O(log n). That's pretty nifty! However, we still don't have decrease-key working yet. That's going to be the challenging part.

Step Two: Implementing Decrease-Key

Right now, we have a "lazy binomial heap" rather than a Fibonacci heap. The real change between a binomial heap and a Fibonacci heap is how we implement decrease-key.

Recall that the decrease-key operation should take an entry already in the heap (usually, we'd have a pointer to it) and a new priority that's lower than the existing priority. It then changes the priority of that element to the new, lower priority.

We can implement this operation very quickly (in time O(log n)) using a straightforward algorithm. Take the element whose key should be decreased (which can be located in O(1) time; remember, we're assuming we have a pointer to it) and lower its priority. Then, repeatedly swap it with its parent node as long as its priority is lower than its parent, stopping when the node comes to rest or when it reaches the root of the tree. This operation takes time O(log n) because each tree has height at most O(log n) and each comparison takes time O(1).

Remember, though, that we're trying to do even better than this - we want the runtime to be O(1)! That's a very tough bound to match. We can't use any process that will move the node up or down the tree, since those trees have heights that can be Ω(log n). We'll have to try something more drastic.

Suppose that we want to decrease the key of a node. The only way that the heap property will be violated is if the node's new priority is lower than that of its parent. If we look at the subtree rooted at that particular node, it will still obey the heap property. So here's a totally crazy idea: what if whenever we decrease the key of a node, we cut the link to the parent node, then bring the entire subtree rooted at the node back up to the top level of the tree?

Modification 4: Have decrease-key decrease the key of a node and, if its priority is smaller than its parent's priority, cut it and add it to the root list.

What will the effect of this operation be? Several things will happen.

1. The node that previously had our node as a child now thinks it has the wrong number of children. Recall that a binomial tree of order n is defined to have n children, but that's not true any more.
2. The collection of trees in the root list will go up, increasing the cost of future dequeue operations.
3. The trees in our heap aren't necessarily going to be binomial trees any more. They might be "formerly" binomial trees that lost children at various points in time.

Number (1) isn't too much of a problem. If we cut a node from its parent, we can just decrease the order of that node by one to indicate that it has fewer children than it thought it previously did. Number (2) also isn't a problem. We can just backcharge the extra work done in the next dequeue-min operation to the decrease-key operation.

Number (3) is a very, very serious issue that we will need to address. Here's the problem: the efficiency of a binomial heap partially stems from the fact that any collection of n nodes can be stored in a collection of Θ(log n) trees of different order. The reason for this is that each binomial tree has 2ⁿ nodes in it. If we can start cutting nodes out of trees, then we risk having trees that have a large number of children (that is, a high order) but which don't have many nodes in them. For example, suppose we start with a single tree of order k and then perform decrease-key operations on all the grandchildren of k. This leaves k as a tree with order k, but which only contains k + 1 total nodes. If we keep repeating this process everywhere, we might end up with a bunch of trees of various orders that have a very small number of children in them. Consequently, when we do our coalesce operation to group the trees together, we might not reduce the number of trees to a manageable level, breaking the Θ(log n)-time bound that we really don't want to lose.

At this point, we're in a bit of a bind. We need to have a lot of flexibility with how the trees can be reshaped so that we can get the O(1) time decrease-key functionality, but we can't let the trees get reshaped arbitrarily or we will end up with decrease-key's amortized runtime increasing to something greater than O(log n).

The insight needed - and, quite honestly, what I think is the real genius in the Fibonacci heap - is a compromise between the two. The idea is the following. If we cut a tree from its parent, we're already planning on decreasing the rank of the parent node by one. The problem really arises when a node loses a lot of children, in which case its rank decreases significantly without any nodes higher up in the tree knowing about it. Therefore, we will say that each node is only allowed to lose one child. If a node loses a second child, then we'll cut that node from its parent, which propagates the information that nodes are missing higher up in the tree.

It turns out that this is a great compromise. It lets us do decrease-keys quickly in most contexts (as long as the nodes aren't children of the same tree), and only rarely do we have to "propagate" a decrease-key by cutting a node from its parent and then cutting that node from its grandparent.

To keep track of which nodes have lost children, we'll assign a "mark" bit to each node. Each node will initial have the mark bit cleared, but whenever it loses a child it will have the bit set. If it loses a second child after the bit has already been set, we'll clear the bit, then cut the node from its parent.

Modification 5: Assign a mark bit to each node that is initially false. When a child is cut from an unmarked parent, mark the parent. When a child is cut from a marked parent, unmark the parent and cut the parent from its parent.

In this older Stack Overflow question, I've sketched out a proof that shows that if trees are allowed to be modified in this way, then any tree of order n must contain at least Θ(φⁿ) nodes, where φ is the golden ratio, about 1.61. This means that the number of nodes in each tree is still exponential in the order of the tree, though it's a lower exponent from before. As a result, the analysis we did earlier about the time complexity of the decrease-key operation still holds, though the term hidden in the Θ(log n) bit will be different.

There's one very last thing to consider - what about the complexity of decrease-key? Previously, it was O(1) because we just cut the tree rooted at the appropriate node and moved it to the root list. However, now we might have to do a "cascading cut," in which we cut a node from its parent, then cut that node from its parent, etc. How does that give O(1) time decrease-keys?

The observation here is that we can add a "charge" to each decrease-key operation that we can then spend to cut the parent node from its parent. Since we only cut a node from its parent if it's already lost two children, we can pretend that each decrease-key operation pays for the work necessary to cut its parent node. When we do cut the parent, we can charge the cost of doing so back to one of the earlier decrease-key operations. Consequently, even though any individual decrease-key operation might take a long time to finish, we can always amortize the work across the earlier calls so that the runtime is amortized O(1).

Step Three: Linked Lists Abound!

There is one final detail we have to talk about. The data structure I've described so far is tricky, but it doesn't seem catastrophically complicated. Fibonacci heaps have a reputation for being fearsome... why is that?

The reason is that in order to implement all of the operations described above, the tree structures need to be implemented in very clever ways.

Typically, you'd represent a multiway tree either by having each parent point down to all the children (perhaps by having an array of children) or by using the left-child/right-sibling representation, where the parent has a pointer to one child, which in turn points to a list of the other children. For a binomial heap, this is perfect. The main operation we need to do on trees is a join operation in which we make one root node a child of another, so it's perfectly reasonable to the pointers in the tree directed from parents to children.

The problem in a Fibonacci heap is that this representation is inefficient when considering the decrease-key step. Fibonacci heaps need to support all the basic pointer manipulations of a standard binomial heap and the ability to cut a single child from a parent.

Consider the standard representations of multiway trees. If we represent the tree by having each parent node store an array or list of pointers to its children, then we can't efficiently (in O(1)) remove a child node from the list of children. In other words, the runtime for decrease-key would be dominated by the bookkeeping step of removing the child rather than the logical step of moving a subtree to the root list! The same issue appears in the left-child, right-sibling representation.

The solution to this problem is to store the tree in a bizarre fashion. Each parent node stores a pointer to a single (and arbitrary) one of its children. The children are then stored in a circularly-linked list, and each points back up to its parent. Since it's possible to concatenate two circularly-linked lists in O(1) time and to insert or remove a single entry from one in O(1) time, this makes it possible to efficiently support the necessary tree operations:

• Make one tree a child of another: if the first tree has no children, set its child pointer to point to the second tree. Otherwise, splice the second tree into the circularly-linked child list of the first tree.

• Remove a child from a tree: splice that child node out of the linked list of children for the parent node. If it's the single node chosen to represent the children of the parent node, choose one of the sibling nodes to replace it (or set the pointer to null if it's the last child.)

There are absurdly many cases to consider and check when performing all these operations simply due to the number of different edge cases that can arise. The overhead associated with all the pointer juggling is one of the reasons why Fibonacci heaps are slower in practice than their asymptotic complexity might suggest (the other big one is the logic for removing the minimum value, which requires an auxiliary data structure).

Modification 6: Use a custom representation of the tree that supports efficient joining of trees and cutting one tree from another.

Conclusion

I hope this answer sheds some light on the mystery that is the Fibonacci heap. I hope that you can see the logical progression from a simpler structure (the binomial heap) to a more complex structure by a series of simple steps based on reasonable insights. It's not unreasonable to want to make insertions amortized-efficient at the expense of deletions, and it's similarly not too crazy to implement decrease-key by cutting out subtrees. From there, the rest of the details are in ensuring that the structure is still efficient, but they're more consequences of the other parts rather than causes.

If you're interested in learning more about Fibonacci heaps, you may want to check out this two-part series of lecture slides. Part one introduces binomial heaps and shows how lazy binomial heaps work. Part two explores Fibonacci heaps. These slides go into more mathematical depth than what I've covered here.

Hope this helps!

这篇关于斐波纳契堆数据结构背后的直觉是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！