我读过维基百科上关于斐波那契堆的文章，也读过CLRS对数据结构的描述，但它们几乎没有提供这种数据结构为什么有效的直觉。为什么斐波那契堆是这样设计的？它们是如何工作的？
谢谢！
这个答案会很长，但我希望它能帮助我们深入了解Fibonacci堆的来源。我假设你已经熟悉二项式堆和摊销分析了。
动机：为什么斐波那契堆积
在进入斐波那契堆之前，最好先探究一下为什么我们首先需要它们。还有很多其他类型的堆(例如，二进制堆和二项式堆)，那么我们为什么需要另一个呢？
主要原因在于Dijkstra算法和Prim算法。这两种图算法都通过维护一个优先级队列来工作，该队列包含具有相关优先级的节点。有趣的是，这些算法依赖于一个名为reduce-key的堆操作，该操作获取优先级队列中已经存在的条目，然后降低其密钥(即增加其优先级)。事实上，这些算法的很多运行时间都是通过调用reduce键的次数来解释的。如果我们能够建立一个优化递减密钥的数据结构，我们就可以优化这些算法的性能。在二进制堆和二项式堆的情况下，减少密钥需要时间O(logn)，其中n是优先级队列中的节点数。如果我们能把它降到O(1)，那么Dijkstra算法和Prim算法的时间复杂性将从O(m-logn)降到(m+n-logn)，这比以前渐近地快。因此，尝试构建一个有效支持减少密钥的数据结构是有意义的。
考虑设计更好的堆结构还有另一个原因。将元素添加到空二进制堆时，每次插入都需要时间O(logn)。如果我们提前知道所有n个元素，就有可能在时间O(n)内构建一个二进制堆，但如果元素以流的形式到达，这是不可能的。在二项式堆的情况下，插入n个连续元素每个元素需要分摊时间O(1)，但如果插入与删除交错，则插入可能最终每个元素需要Ω(logn)时间。因此，我们可能希望搜索一个优先级队列实现，该实现优化插入以使每次插入花费O(1)时间。
第一步：懒惰的二项式堆
为了开始构建Fibonacci堆，我们将从二项式堆开始，并对其进行修改，以使插入花费时间O(1)。尝试这种方法并非完全不合理——毕竟，如果我们要进行大量插入而不是那么多出队列，那么优化插入是有意义的。
如果您还记得的话，二项式堆的工作原理是将堆中的所有元素存储在二项式树的集合中。n阶的二叉树中有2个n节点，堆是作为二叉树集合的结构，所有二叉树都服从堆属性。通常，二项式堆中的插入算法如下所示：
- 创建一个新的singleton节点(这是一个顺序为0的树)
- 如果存在顺序为0的树：
- 将两个0阶树合并为1阶树
- 如果存在1阶树：
- 将两个顺序为1的树合并为一个顺序为2的树
- 如果存在2阶树：
此过程确保在每个时间点，每个订单最多有一个树。由于每棵树所包含的节点都比其顺序多出指数级，这确保了树的总数很小，这使得出队列可以快速运行(因为在执行出队列最小步骤后，我们不必查看太多不同的树)。
然而，这也意味着，将节点插入二项式堆的最坏运行时间是Θ(logn)，因为我们可能有需要合并在一起的Θ(log n)树。这些树需要合并在一起，只是因为我们在执行出列步骤时需要将树的数量保持在较低水平，而且在未来的插入中保持较低的树数量绝对没有好处。
这引入了二项式堆的第一个出发点：
修改1：将节点插入堆时，只需创建一个顺序为0的树，并将其添加到现有的树集合中。不要将树木合并在一起。
我们还可以进行另一项更改。通常，当我们将两个二项式堆合并在一起时，我们会执行合并步骤，以确保在生成的树中每个顺序最多有一棵树。同样，我们进行这种压缩是为了快速出队，合并操作不需要为此付费。因此，我们将进行第二次更改：
修改2：将两个堆合并在一起时，只需将它们的所有树合并在一起，而不进行任何合并。不要将任何树木合并在一起。
如果我们进行此更改，我们很容易在排队操作中获得O(1)性能，因为我们所做的只是创建一个新节点并将其添加到树集合中。然而，如果我们只做这个更改而不做任何其他事情，我们将完全破坏出列min操作的性能。回想一下，在移除最小值后，出列min需要扫描堆中所有树的根，以便找到最小值。如果我们通过插入Θ(n)个节点来添加这些节点，那么我们的出列操作将不得不花费Θ(n)时间来查看所有这些树。这是一个巨大的性能打击。。。我们能避免吗？
如果我们的插入真的只是添加了更多的树，那么我们所做的第一次出列肯定需要Ω(n)时间。然而，这并不意味着每个出队列都必须是昂贵的。如果在进行出列后，我们将堆中的所有树合并在一起，使得每个顺序只有一棵树，会发生什么？最初这将需要很长时间，但如果我们开始连续进行多个出队列，那么未来的出队列将明显更快，因为周围的树更少。
不过，这个设置有一个小问题。在正常的二项式堆中，树总是按顺序存储的。如果我们只是不断地把新的树扔到我们的树集合中，随机地把它们聚在一起，然后再添加更多的树，就不能保证这些树会按任何顺序排列。因此，我们需要一种新的算法来将这些树合并在一起。
该算法背后的直觉如下。假设我们创建一个从树顺序映射到树的哈希表。然后，我们可以对数据结构中的每棵树进行以下操作：
- 向上查找，看看是否已经有了该顺序的树
- 如果没有，请将当前树插入哈希表中
- 否则：
- 将当前树与该顺序的树合并，从哈希表
- 递归地重复此过程
此操作确保完成后，每个订单最多有一个树。它也相对高效。假设我们从T个总树开始，到T个总树结束。我们最终要进行的合并总数将是T-T-1，每次进行合并都需要O(1)时间。因此，此操作的运行时间将是树的数量(每棵树至少访问一次)加上完成的合并数量的线性。
如果树的数量很小(比如说，Θ(logn))，那么这个操作将只需要时间O(log n)。如果树的数量很大(比如说，Θ(n))，那么这个操作将花费Θ(n)时间，但只剩下Θ(logn)棵树，这将使未来的出列速度更快。
我们可以通过摊销分析和使用潜在函数来量化事情会变得更好。设Φ为我们的势函数，设Φ为数据结构中的树数。这意味着操作成本如下：
- 插入：O(1)是否起作用，并将电势增加一。摊销成本为O(1)
- 合并：O(1)是否有效。一个堆的电位下降到0，另一个堆电位增加相应的量，因此电位没有净变化。因此，摊余成本为O(1)
- Dequeue Min：O(#trees+#merges)是否有效，并将势能降低到θ(logn)，即如果我们急切地将树合并在一起，我们在二项式树中的树数。我们可以用不同的方式来解释这一点。让我们把树的数量写成Θ(logn)+E，其中E是"；过量"；树木数量。在这种情况下，完成的总工作量为Θ(logn+E+#合并)。请注意，我们将对每个多余的树进行一次合并，因此完成的总工作量为Θ(logn+E)。由于我们的势使树的数量从Θ(logn)+E下降到Θ(log n)，所以势的下降是-E。因此，出列最小值的摊余成本为Θ(logn)
另一种直观的方法是通过观察为什么我们有多余的树来了解出列最小值的摊余成本是θ(logn)。这些额外的树之所以存在，是因为那些贪婪的插件正在制造所有这些额外的树木，却没有为此付费！因此，我们可以"；反向充电"；与将所有合并返回到占用所有时间的单个插入相关联的成本；核心"；操作和一堆其他操作，我们将把它们归咎于插入。
因此：
修改3：在出列最小操作中，合并所有树以确保每个订单最多有一棵树。
此时，我们在时间O(1)中运行插入和合并，在摊销时间O(logn)中运行出队列。真漂亮！然而，我们仍然没有减少关键工作。这将是具有挑战性的部分。
第二步：实施减量键
现在，我们有一个"；惰性二项式堆"；而不是斐波那契堆。二项式堆和斐波那契堆之间的真正变化是我们如何实现递减键。
回想一下，减少键操作应该采用堆中已经存在的一个条目(通常，我们会有一个指向它的指针)和一个低于现有优先级的新优先级。然后，它将该元素的优先级更改为新的较低优先级。
我们可以使用简单的算法非常快速地(在时间O(logn))实现此操作。取键应该减少的元素(可以位于O(1)时间内；记住，我们假设我们有一个指向它的指针)并降低它的优先级。然后，只要其优先级低于其父节点，就反复将其与其父节点交换，当节点静止或到达树根时停止。此操作需要时间O(logn)，因为每棵树的高度最多为O(log n)，并且每次比较需要时间O。
不过，请记住，我们正在努力做得更好——我们希望运行时为O(1)！这是一个很难匹配的。我们不能使用任何将节点在树上向上或向下移动的过程，因为这些树的高度可以是Ω(logn)。我们得试试更激烈的办法。
假设我们想要减少一个节点的键。违反堆属性的唯一方法是节点的新优先级低于其父节点的优先级。如果我们观察根在该特定节点上的子树，它仍然服从堆属性。因此，这里有一个完全疯狂的想法：如果每当我们减少一个节点的键时，我们都会切断到父节点的链接，然后将植根于该节点的整个子树带回树的顶层，会怎么样？
修改4：使用减少键减少节点的键，如果其优先级小于其父节点的优先级，则将其剪切并添加到根列表中。
此操作的效果如何？会发生一些事情。
- 以前将我们的节点作为子节点的节点现在认为它有错误数量的子节点。回想一下，n阶的二项式树被定义为有n个子树，但现在已经不是这样了
- 根列表中的树集合将增加，这将增加未来出列操作的成本
- 我们堆中的树不一定是二项式树了。它们可能是"；以前的"；在不同时间点失去孩子的二项式树
数字(1)不是太大问题。如果我们从其父节点中剪切一个节点，我们可以将该节点的顺序减少一，以表明它的子节点比以前认为的要少。数字(2)也不是问题。我们可以将下一次出列min操作中完成的额外工作倒充到reduce-key操作中。
数字(3)是一个非常、非常严重的问题，我们需要解决。问题是：二项式堆的效率部分源于这样一个事实，即任何n个节点的集合都可以存储在不同阶的Θ(logn)树的集合中。原因是每个二项式树中都有2个n节点。如果我们可以开始从树中删除节点，那么我们就有可能拥有有大量子节点(即高阶)但其中没有太多节点的树。例如，假设我们从k阶的一棵树开始，然后对k的所有子树执行递减键运算。这使得k成为一棵k阶的树，但它只包含k+1个总节点。如果我们到处重复这个过程，我们可能会得到一堆不同层次的树，其中只有极少数的子树。因此，当我们进行合并操作将树分组在一起时，我们可能无法将树的数量减少到可管理的水平，从而打破了我们真正不想失去的θ(logn)-时间限制。
在这一点上，我们有点不知所措。我们需要在如何重塑树方面有很大的灵活性，这样我们就可以获得O(1)时间递减键的功能，但我们不能让树任意重塑，否则递减键的摊销运行时间将增加到大于O(logn)的值。
所需要的洞察力——老实说，我认为这才是斐波那契堆中真正的天才——是两者之间的妥协。想法如下。如果我们从父节点上切下一棵树，我们已经计划将父节点的秩降低一。当一个节点失去了很多子节点时，问题就真正出现了，在这种情况下，它的排名显著下降，而树中任何更高的节点都不知道它。因此，我们将说每个节点只允许失去一个子节点。如果一个节点失去了第二个子节点，那么我们将从其父节点中剪切该节点，这将传播节点在树中丢失的信息。
事实证明，这是一个伟大的妥协。它允许我们在大多数上下文中快速减少关键帧(只要节点不是同一棵树的子节点)，而且很少需要"减少关键帧"；传播"；通过从其父节点上剪切一个节点，然后从其祖父母节点上剪切该节点，可以使用减少键。
为了跟踪哪些节点丢失了子节点，我们将在；标记"；位到每个节点。每个节点最初都会清除标记位，但无论何时丢失子节点，都会设置该位。如果它在位已经设置之后丢失了第二个子节点，我们将清除位，然后从其父节点中剪切节点。
修改5：为每个最初为false的节点分配一个标记位。从未标记的父对象剪切子对象时，请标记该父对象。从标记的父对象中剪切子对象时，取消标记父对象并从其父对象中剪切父对象。
在这个CS理论堆栈交换问题和这个旧的堆栈溢出问题)个节点，其中φ是黄金比例，约为1.61。这意味着每棵树中的节点数量仍然是按树的顺序排列的指数，尽管它比以前的指数更低。因此，我们之前对递减键操作的时间复杂性所做的分析仍然成立，尽管隐藏在θ(logn)位中的项将不同。
还有最后一件事需要考虑——递减键的复杂性如何？以前，它是O(1)，因为我们只是剪切在适当节点上生根的树，并将其移动到根列表中。然而，现在我们可能不得不做一个"；级联切割；其中，我们从其父节点中剪切一个节点，然后从父节点中剪切该节点，等等。这如何给出O(1)时间减少键？
这里的观察结果是，我们可以添加一个"；电荷"；对于每个减少键操作，然后我们可以花费这些操作来从其父节点中剪切父节点。由于只有在节点已经失去两个子节点的情况下，我们才能从其父节点中剪切节点，因此我们可以假设每个减少键操作都会为剪切其父节点所需的工作付费。当我们确实削减了母级时，我们可以将这样做的成本收回到早期的减少关键操作中。因此，即使任何单独的减少键操作都可能需要很长时间才能完成，我们也可以始终在早期调用中分摊工作，以便运行时分摊O(1)。
第三步：链表Abound
还有最后一个细节我们必须谈谈。到目前为止，我描述的数据结构很棘手，但它似乎并不复杂。斐波那契堆以可怕著称。。。为什么？
原因是为了实现上述所有操作，树结构需要以非常巧妙的方式来实现。
通常，您可以通过使每个父级向下指向所有子级(可能是通过具有子级数组)或使用左子级/右同级表示来表示多路树，其中父级有一个指向一个子级的指针，而该指针又指向其他子级的列表。对于二项式堆，这是完美的。我们需要在树上进行的主要操作是连接操作，在该操作中，我们将一个根节点作为另一个根的子节点，因此树中从父节点指向子节点的指针是完全合理的。
Fibonacci堆中的问题是，当考虑减少关键步骤时，这种表示是低效的。Fibonacci堆需要支持标准二项式堆的所有基本指针操作和从父堆中剪切单个子堆的能力。
考虑多路树的标准表示。如果我们通过让每个父节点存储指向其子节点的指针数组或列表来表示树，那么我们就不能有效地(在O(1)中)从子节点列表中删除子节点。换句话说，reduce键的运行时将由删除子项的记账步骤主导，而不是将子树移动到根列表的逻辑步骤！同样的问题也出现在左子女、右兄弟姐妹的表示中。
这个问题的解决方案是以一种奇怪的方式存储树。每个父节点都存储一个指向其单个(任意)子节点的指针。然后，子项存储在一个循环链接列表中，每个子项都指向其父项。由于可以在O(1)时间内连接两个循环链表，并在O(2)时间内插入或删除一个条目，因此可以有效地支持必要的树操作：
使一棵树成为另一棵树的子树：如果第一棵树没有子树，则将其子指针设置为指向第二棵树。否则，将第二棵树拼接到第一棵树的循环链接子列表中。从树中移除子节点：将该子节点从父节点的子节点链接列表中拼接出来。如果它是被选择来表示父节点的子节点的单个节点，则选择其中一个同级节点来替换它(或者如果它是最后一个子节点，则将指针设置为null)
在执行所有这些操作时，由于可能出现的不同边缘情况的数量，需要考虑和检查的情况非常多。与所有指针杂耍相关的开销是Fibonacci堆在实践中比其渐进复杂性可能暗示的慢的原因之一(另一个大的原因是去除最小值的逻辑，这需要辅助数据结构)。
修改6：使用树的自定义表示，支持高效连接树和从另一棵树中剪切一棵树。
结论
我希望这个答案能揭示斐波那契堆的奥秘。我希望你能通过一系列基于合理见解的简单步骤，看到从更简单的结构(二项式堆)到更复杂的结构的逻辑进展。想要以删除为代价使插入高效摊销并非没有道理，同样，通过删除子树来实现reduce键也不太疯狂。从那里开始，其余的细节是为了确保结构仍然有效，但它们更多的是其他部分的后果，而不是原因。
如果你有兴趣了解更多关于斐波那契堆的知识，你可能想看看这两部分的系列讲座幻灯片。第一部分介绍了二项式堆，并展示了惰性二项式堆栈是如何工作的。第二部分探讨斐波那契堆。这些幻灯片的数学深度比我在这里介绍的要深。