斐波那契堆数据结构背后的直觉是什么？
我已经阅读了关于Fibonacci堆的维基百科文章，并阅读了CLRS对数据结构的描述，但是他们对这个数据结构为什么不起作用。 为什么斐波那契堆是按照它们的方式devise的？ 他们如何工作？
谢谢！
这个答案将会相当长，但是我希望它能帮助我们提供一些关于Fibonacci堆来自哪里的信息。 我假设你已经熟悉二项堆和分期分析 。
动机：为什么斐波纳契堆？
在跳进斐波那契堆之前，首先探究为什么我们甚至需要它们可能是很好的。 还有很多其他types的堆（例如二元堆和二元堆 ），那么为什么还需要另一堆 ？
主要原因在于Dijkstraalgorithm和Primalgorithm 。 这两种图algorithm都是通过维护一个拥有相关优先级的优先级队列来工作的。 有趣的是，这些algorithm依赖于一个叫做reduce-key的堆操作，它将一个已经存在于优先级队列中的条目，然后减less它的键（即增加它的优先级）。 事实上，这些algorithm的运行时间很多是由你必须调用递减键的次数来解释的。 如果我们可以构build一个优化减less密钥的数据结构，我们可以优化这些algorithm的性能。 在二进制堆和二项堆的情况下，减less键需要时间O（log n），其中n是优先级队列中的节点数。 如果我们把它放到O（1）中，那么Dijkstraalgorithm和Primalgorithm的时间复杂度就会从O（m log n）下降到（m + n log n），这比以前渐近地快了。 因此，尝试构build支持递减键的数据结构是有意义的。
还有一个理由考虑devise一个更好的堆结构。 将元素添加到空的二进制堆时，每个插入需要花费时间O（log n）。 如果我们事先知道所有的n个元素，就可以在时间O（n）上build立一个二进制堆 ，但是如果元素到达一个stream中，这是不可能的。 在二项堆的情况下，插入n个连续元素分别花费时间O（1），但是如果插入与删除交错，插入可能最终每个都会花费Ω（log n）个时间。 因此，我们可能想要search一个优化插入的优先级队列实现，每次需要时间O（1）。
第一步：懒惰的二项式堆
为了开始构build斐波那契堆，我们将从一个二叉堆开始，并修改它以使插入花费时间O（1）。 尝试这一点并不是没有道理的 – 毕竟，如果我们要做大量的插入操作而不是那么多的出列，那么优化插入是有意义的。
如果您还记得，二叉堆是通过将所有元素存储在一堆二叉树中的堆中工作的。 n阶二叉树中有2个n个节点，堆结构为二叉树的集合，均遵循heap属性。 通常，二项堆中的插入algorithm的工作方式如下：
- 创build一个新的单例节点（这是一棵0号树）。
- 如果有一个命令树0：
- 将0号两棵树合并成一棵1号树。
- 如果有一棵树1：
- 将1号树的两棵树合并成一棵树号2。
- 如果有2号树：
- …
这个过程确保在每个时间点，每个订单最多只有一棵树。 由于每棵树比其秩序指数地增加了多个节点，这就保证了树的总数量很小，这样可以使得出队快速运行（因为我们不需要在出队分步之后查看太多不同的树）。
但是，这也意味着将节点插入二项堆的最坏情况运行时间是Θ（log n），因为我们可能有需要合并在一起的Θ（log n）树。 那些树需要合并在一起，只是因为在进行一个出列步骤时我们需要保持较低的树木数量，而且在未来的插入中保持较低的树木数量是绝对没有好处的。
这引入了二叉堆的第一个出发点：
修改1 ：向堆中插入节点时，只需创build一个0号树，并将其添加到现有树的集合中。 不要把树合并在一起。
我们可以做出另一个改变。 通常，当我们将两个二项堆合并在一起时，我们会执行一个合并步骤，将它们合并到一起，以确保生成的树中每个顺序最多有一棵树。 再次，我们这样做压缩，以便出队速度很快，没有真正的理由为什么合并操作应该支付这一点。 因此，我们会做第二个改变：
修改2 ：将两个堆合并在一起时，将所有的树合并在一起，不要合并。 不要合并任何树木。
如果我们做这个改变，我们很容易在排队操作上执行O（1），因为我们所做的只是创build一个新节点并将其添加到树的集合中。 但是，如果我们只是做这个改变而不做别的事情，那么我们完全破坏了出队 – 分钟运行的performance。 回想一下，在删除最小值之后，出队min需要遍历堆中所有树的根，以便find最小值。 如果我们通过插入它们来添加Θ（n）节点，那么我们的出队操作将不得不花费Θ（n）时间来查看所有这些树。 这是一个巨大的性能打击…我们可以避免它？
如果我们的插入真的只是添加更多的树，那么我们所做的第一个出列肯定会花费Ω（n）的时间。 但是，这并不意味着每个出队都必须是昂贵的。 如果在做出列队之后，我们将堆中的所有树合并在一起，结果每个命令只有一棵树？ 这将需要很长时间，但如果我们开始连续多次出队，那么未来的出队将显着加快，因为周围的树木越来越less。
虽然这个设置有一个小问题。 在正常的二项堆中，树总是按顺序存储的。 如果我们不断地把新树插入我们的树木集合中，随机合并它们，然后再增加更多的树木，那么不能保证树木会以任何顺序。 因此，我们需要一个新的algorithm来将这些树合并在一起。
这个algorithm背后的直觉是如下。 假设我们创build一个哈希表，从树形结构树到树形结构。 然后我们可以对数据结构中的每个树执行以下操作：
- 看看是否已经有一个这样的顺序树。
- 如果不是，则将当前树插入哈希表中。
- 除此以外：
- 将当前树与该顺序的树合并，从哈希表中删除旧的树。
- recursion地重复这个过程。
这个操作确保当我们完成时，每个订单最多只有一棵树。 这也相对有效。 假设我们从T棵树开始，并以t棵树结束。 我们最终完成的合并次数为T-t-1，每次合并时，都需要O（1）的时间来完成。 因此，此操作的运行时间将与树的数量（每个树至less访问一次）加上完成的合并次数成线性关系。
如果树的数量很less（比如Θ（log n）），那么这个操作只需要O（log n）的时间。 如果树的数量很大（比如Θ（n）），那么这个操作将花费Θ（n）时间，但是只剩下Θ（log n）树，使得将来的出队更快。
我们可以通过做一个分期分析和使用一个潜在的函数来量化多less更好的东西。 设Φ是我们的潜在函数，令Φ是数据结构中树的数量。 这意味着运营成本如下：
- 插入 ：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。 因此，出队分摊的成本是Θ（log n）。
另一个直观的方法就是看看为什么分离出的分摊成本是Θ（log n）是为什么我们有剩余的树。 这些额外的树木在那里，因为那些贪婪的插入正在使所有这些额外的树木，而不是为他们付出！ 因此，我们可以将与所有合并相关联的成本“回充”回到所有时间占用的个体插入，而留下了Θ（log n）“核心”操作以及我们将要指责的一系列其他操作插入。
因此：
修改3 ：在出队 – 分钟操作中，合并所有树木以确保每个订单至多有一棵树。
在这一点上，我们已经插入和合并运行时间O（1），并在摊销时间O（log n）出列运行。 这很漂亮！ 但是，我们还没有减less关键的工作。 这将是具有挑战性的部分。
第二步：实施降低关键
现在，我们有一个“懒惰的二项式堆”，而不是斐波纳契堆。 二项堆和斐波那契堆之间的真正变化是我们如何实现减键。
回想一下，reduce-key操作应该在堆中已经有一个入口（通常我们有一个指向它的指针）和一个低于现有优先级的新的优先级。 然后将该元素的优先级更改为新的较低优先级。
我们可以使用一个简单的algorithm非常快速地（在时间O（log n））实现这个操作。 拿钥匙应该减less的元素（可以位于O（1）次;记住，我们假设我们有一个指针）并降低它的优先级。 然后，只要它的优先级低于父节点，就会反复交换它的父节点，当节点停止或到达树的根时停止。 这个操作花费时间O（log n），因为每棵树的高度最多为O（log n），每个比较花费时间O（1）。
记住，尽pipe如此，我们试图做得比这更好 – 我们希望运行时为O（1）！ 这是一个非常艰难的匹配。 我们不能使用任何将节点向上或向下移动的进程，因为这些树的高度可能是Ω（log n）。 我们将不得不尝试更激烈的事情。
假设我们想减less一个节点的密钥。 堆属性将被违反的唯一方法是节点的新优先级低于其父节点的优先级。 如果我们查看以特定节点为根的子树，它仍然会遵守heap属性。 所以这里有一个非常疯狂的想法：如果每当我们减less一个节点的密钥，我们就切断到父节点的链接，然后把在节点上扎根的整个子树恢复到树的顶层？
修改4 ：减less键减less节点的键，如果其优先级小于其父节点的优先级，则将其剪切并添加到根节点列表中。
这个操作的效果是什么？ 有几件事情会发生。
- 以前有我们的节点作为孩子的节点现在认为它有错误的孩子数量。 回想一下，n阶二叉树被定义为有n个孩子，但这不再是真的。
- 根目录中树木的收集将会增加，增加了未来出列操作的成本。
- 我们堆里的树木不一定会变成二叉树。 他们可能是“以前”的二叉树，在不同的时间点失去了孩子。
数字（1）不是太多的问题。 如果我们从其父节点中删除一个节点，我们可以将该节点的顺序减1，以表示它的子节点比它以前所做的要less。 数量（2）也不是问题。 我们可以将在下一个出队 – 分钟操作中完成的额外工作重新加载到减less键操作。
数量（3）是一个非常非常严重的问题，我们需要解决。 问题在于：二项堆的效率部分源于n个节点的集合可以存储在不同顺序的Θ（log n）树中的事实。 原因是每个二叉树在其中有2 个n个节点。 如果我们可以从树上切割节点，那么我们冒着拥有大量子节点（即高阶）但是没有多less节点的树木的风险。 例如，假设我们从k阶的单个树开始，然后对k的所有孙子执行减less键操作。 这使k作为k阶的树，但只包含k + 1个总节点。 如果我们不断地重复这个过程，那么我们可能会得到一堆各种命令的树，其中有很less的孩子。 因此，当我们进行聚合操作将树分组在一起时，我们可能不会将树的数量减less到可控的水平，从而打破了我们实际上不想丢失的Θ（log n）时间界限。
在这一点上，我们有点困难。 我们需要在树的重构方面有很大的灵活性，这样我们就可以获得O（1）的时间减less键的function，但是我们不能让树被任意的重新塑造，键的分期运行时间增加到大于O（log n）的值。
需要的洞察力 – 老实说，我认为是斐波那契堆中真正的天才 – 是两者之间的妥协。 这个想法如下。 如果我们从父母那里砍树，我们已经计划将父节点的等级降低一级。 当一个节点失去了很多孩子时，这个问题真的出现了，在这种情况下，树的等级显着下降，树中的任何节点都没有更高的知道。 因此，我们会说每个节点只允许失去一个孩子。 如果一个节点失去了第二个子节点，那么我们将从其父节点中删除该节点，从而传播节点在树中较高的信息。
事实certificate，这是一个很大的妥协。 它让我们可以在大多数情况下快速实现递减键（只要节点不是同一棵树的子节点），而且我们很less必须通过从父节点切割节点来“传播”减less键，然后从祖父母切割该节点。
为了跟踪哪些节点丢失了孩子，我们将为每个节点分配一个“标记”位。 每个节点将首先清除标记位，但每当它失去一个孩子，它将设置位。 如果在已经设置位后丢失了第二个孩子，我们将清除该位，然后从其父节点中删除该节点。
修改5 ：将标记位分配给每个最初为false的节点。 从未标记的父母切下孩子时，请标记父母。 当一个孩子从一个标记的父母被切断时，取消父母的标记并从父母中切除父母。
在这个较旧的堆栈溢出问题中 ，我已经勾画出一个certificate，表明如果允许以这种方式修改树，那么任何n阶树必须包含至lessΘ（φn）个节点，其中φ是金比例约为1.61。 这意味着每棵树中的节点数仍然是树的顺序的指数，虽然它是一个较低的指数。 因此，尽pipe隐藏在Θ（log n）位中的术语将会不同，但我们之前对减less密钥操作的时间复杂性的分析仍然成立。
还有最后一件事要考虑 – 减less键的复杂性呢？ 以前，它是O（1），因为我们只是剪切了根节点上的树，并将它移到了根列表中。 然而，现在我们可能不得不做一个“级联剪切”，在这个剪切中，我们从父节点中切出一个节点，然后从父节点中删除这个节点，等等如何给O（1）个时间减键？
这里的观察是，我们可以为每个减less键操作添加一个“费用”，然后我们可以花费从其父节点中删除父节点。 因为如果已经失去了两个孩子，我们只能从父节点中删除一个节点，所以我们可以假设每个减键操作都支付切割其父节点所需的工作。 当我们切断父母时，我们可以将这样做的成本收回到早先的减less操作之一。 因此，即使任何单独的减键操作可能需要很长时间才能完成，我们总是可以在早期的调用中分摊工作，以便运行时分摊到O（1）。
第三步：链接列表比比皆是！
有一个最后的细节我们必须谈论。 到目前为止，我所描述的数据结构是棘手的，但它似乎并不是灾难性的复杂。 斐波那契堆有一个可怕的声誉…为什么呢？
原因是为了实现上述所有的操作，树结构需要以非常聪明的方式来实现。
通常情况下，通过让每个父节点指向所有子节点（可能通过有一组子节点）或使用左节点/右节点表示forms （其中父节点具有指向一个孩子，这反过来指向其他孩子的名单。 对于二项堆来说，这是完美的。 我们需要在树上做的主要操作是一个连接操作，在这个连接操作中，我们将一个根节点作为另一个的子节点，所以对于从父母到孩子的树中的指针是完全合理的。
Fibonacci堆中的问题是，在考虑减less关键步骤时，这种表示效率低下。 斐波那契堆需要支持标准二项堆的所有基本指针操作， 并且能够从父项中切除单个子项。
考虑多路树的标准表示。 如果我们通过让每个父节点存储一个指向它的子节点的数组或指针列表来表示树，那么我们不能有效地（在O（1）中）从子节点列表中删除一个子节点。 换句话说，减less密钥的运行时间将由删除孩子的簿记步骤支配，而不是将子树移动到根列表的逻辑步骤！ 同样的问题出现在左孩子，右兄弟姐妹的代表中。
解决这个问题的方法是把树存储在一个奇怪的方式。 每个父节点都存储一个指向其单个（任意）子节点的指针。 然后将孩子们存放在一个循环链表中，每个孩子都回到父母身上。 由于可以在O（1）时间内连接两个循环链表，并在O（1）时间内插入或删除一个条目，因此可以有效地支持必要的树操作：
-
使一棵树成为另一棵树：如果第一棵树没有孩子，则将其子指针设置为指向第二棵树。 否则，将第二棵树拼接成第一棵树的循环链接的子列表。
-
从树中删除一个子节点：将子节点从父节点的子节点链表中拼出。 如果select单节点来表示父节点的子节点，则select其中一个兄弟节点来replace它（或者，如果它是最后一个子节点，则将该指针设置为null）。
执行所有这些操作时要考虑和检查的情况是荒谬的，仅仅是由于可能出现的不同边缘情况的数量。 与所有指针杂耍相关的开销是Fibonacci堆在实践中慢于渐近复杂性可能暗示的原因之一（另一个重要原因是去除最小值的逻辑，这需要辅助数据结构）。
修改6 ：使用树的自定义表示，支持树的有效连接和切割另一棵树。
结论
我希望这个答案揭示斐波那契堆的奥秘。 我希望通过一系列基于合理的见解的简单步骤，您可以看到从简单结构（二项堆）到更复杂结构的逻辑进程。 想要以牺牲删除为代价来实现分期高效的插入并不是不合理的，并且通过删除子树来实现减less键也同样不是太疯狂。 从那里，其余的细节是在确保结构仍然有效，但他们更多的其他部分的后果 ，而不是原因 。
如果您有兴趣了解更多关于斐波那契堆的信息，您可能需要查看这个由两部分组成的系列演讲幻灯片。 第一部分介绍了二项堆，并展示了懒惰二项堆是如何工作的。 第二部分探讨斐波那契堆。 这些幻灯片比我在这里介绍的更深入的math深度。
希望这可以帮助！
