斐波那契堆数据结构背后的直觉是什么? [英] What is the intuition behind the Fibonacci heap data structure?
问题描述
我已经阅读了关于斐波那契堆的维基百科文章并阅读了 CLRS 对数据结构的描述，但它们提供的内容很少为什么这个数据结构有效的直觉.为什么斐波那契堆的设计方式如此?它们是如何工作的?
谢谢！
这个答案会很长，但我希望它有助于提供一些关于斐波那契堆来自何处的见解.我假设您已经熟悉二项式堆和摊销分析.
动机:为什么是斐波那契堆?
在进入斐波那契堆之前，最好先探索一下为什么我们甚至需要它们.还有很多其他类型的堆(二进制堆和二项式堆，例如)，那么为什么我们还需要另一个?
主要原因出现在 Dijkstra 的算法 和 Prim 的算法.这两种图算法都通过维护一个优先级队列来工作，该队列包含具有相关优先级的节点.有趣的是，这些算法依赖于一个叫做 decrease-key 的堆操作，它获取一个已经在优先级队列中的条目，然后减少它的键(即增加它的优先级).事实上，这些算法的很多运行时间都是通过调用decrease-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 阶二叉树有 2n 个节点，堆是所有服从堆性质的二叉树的集合结构.通常，二项式堆中的插入算法工作如下:
- 创建一个新的单例节点(这是一棵 0 阶树).
- 如果有一棵 0 阶树:
- 将两棵 0 阶树合并成一棵 1 阶树.
- 如果存在一棵 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) 内运行.真是太巧了！但是，我们仍然没有减少键工作.这将是具有挑战性的部分.
第二步:实现递减键
现在，我们有一个惰性二项式堆"而不是斐波那契堆.二项式堆和斐波那契堆之间的真正变化在于我们如何实现减键.
回想一下，reduce-key 操作应该获取一个已经在堆中的条目(通常，我们会有一个指向它的指针)和一个低于现有优先级的新优先级.然后将该元素的优先级更改为新的、较低的优先级.
我们可以使用简单的算法非常快速地实现这个操作(时间为 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).
所需的洞察力 - 老实说，我认为斐波那契堆中真正的天才 - 是两者之间的妥协.思路如下.如果我们从它的父节点切下一棵树，我们已经计划将父节点的等级降低一.当一个节点失去 lot 个子节点时，问题就会真正出现，在这种情况下，它的排名会显着下降，而树中更高的任何节点都不知道它.因此，我们会说每个节点只允许失去一个孩子.如果一个节点失去了第二个子节点，那么我们将从它的父节点中删除该节点，这会传播节点在树中更高层丢失的信息.
事实证明这是一个很好的妥协.它让我们在大多数情况下快速减少键(只要节点不是同一棵树的子节点)，而且我们很少需要传播"树.通过从其父节点切割节点然后从其祖父节点切割该节点来减少键.
为了跟踪哪些节点丢失了子节点，我们将为其分配一个标记".位到每个节点.每个节点最初都会清除标记位，但是每当它失去一个子节点时，它都会设置该位.如果在该位已经设置后它失去了第二个子节点，我们将清除该位，然后从其父节点中删除该节点.
<块引用>修改 5:为每个最初为假的节点分配一个标记位.当孩子从未标记的父级中切出时，标记父级.当一个孩子从一个被标记的父级中被剪切时，取消父级的标记并将父级从它的父级中剪切掉.
在 这个 CS 理论堆栈交换问题 和 这个较旧的堆栈溢出问题，我已经草拟了一个证明，表明如果允许以这种方式修改树，那么任何 n 阶树必须至少包含 Θ(φn) 个节点，其中 φ 是 黄金比例，约 1.61.这意味着每棵树中的节点数仍然按照树的顺序呈指数增长，尽管它比之前的指数要低.因此，我们之前对减键操作的时间复杂度的分析仍然成立，尽管隐藏在 Θ(log n) 位中的项会有所不同.
还有最后一件事需要考虑 - 减键的复杂性如何?以前，它是 O(1)，因为我们只是切割以适当节点为根的树并将其移动到根列表.然而，现在我们可能不得不做一个级联切割"，其中我们从其父节点中切割一个节点，然后从 其 父节点中切割 那个 节点，等等.这如何给 O(1) 时间减少键?
这里的观察是我们可以添加一个电荷"到每个减少键操作，然后我们可以用它来从父节点中切割父节点.因为我们只在一个节点已经失去两个孩子的情况下从它的父节点中切割一个节点，所以我们可以假设每个减少键操作都会为切割其父节点所需的工作付出代价.当我们确实削减了父级时，我们可以将这样做的成本收回到较早的减键操作之一.因此，即使任何单独的减键操作可能需要很长时间才能完成，但我们总是可以在较早的调用之间分摊工作，以便分摊运行时间 O(1).
第三步:链表比比皆是！
最后还有一个细节要谈.到目前为止，我描述的数据结构很棘手，但它似乎并不复杂.斐波那契堆以可怕而著称……这是为什么?
原因是为了实现上述所有操作，树结构需要以非常巧妙的方式实现.
通常，您可以通过让每个父节点指向所有子节点(也许通过拥有一组子节点)或 使用左孩子/右兄弟表示，其中父有一个指向一个孩子的指针，该指针又指向其他孩子的列表.对于二项式堆，这是完美的.我们需要在树上做的主要操作是连接操作，在这个操作中我们将一个根节点作为另一个根节点的子节点，因此树中从父节点指向子节点的指针是完全合理的.
斐波那契堆中的问题在于，在考虑减少关键步骤时，这种表示是低效的.斐波那契堆需要支持标准二项式堆的所有基本指针操作以及从父项中切出单个子项的能力.
考虑多路树的标准表示.如果我们通过让每个父节点存储一个数组或指向其子节点的指针列表来表示树，那么我们不能有效地(在 O(1) 中)从子节点列表中删除子节点.换句话说，reduce-key 的运行时将由删除子项的簿记步骤而不是将子树移动到根列表的逻辑步骤控制！同样的问题出现在左子、右兄弟的表示中.
这个问题的解决方案是以一种奇怪的方式存储树.每个父节点存储一个指向其单个(和任意)子节点的指针.然后将子项存储在一个循环链接列表中，每个子项都指向其父项.由于可以在 O(1) 时间内连接两个循环链表，并在 O(1) 时间内从一个列表中插入或删除单个条目，因此可以有效地支持必要的树操作:
使一棵树成为另一棵树的子树:如果第一棵树没有子树，则将其子指针设置为指向第二棵树.否则，将第二棵树拼接到第一棵树的循环链接子列表中.
从树中移除子节点:将子节点从父节点的子节点链表中拼接出来.如果是选择代表父节点的子节点的单个节点，则选择其中一个兄弟节点替换它(如果是最后一个子节点，则将指针设置为空.)
仅仅由于可能出现的不同边缘情况的数量，在执行所有这些操作时需要考虑和检查的情况多得荒谬.与所有指针杂耍相关的开销是斐波那契堆在实践中比其渐近复杂度可能暗示的慢的原因之一(另一个重要原因是删除最小值的逻辑，这需要辅助数据结构).<块引用>
修改 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 2n 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.
- 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.
- The collection of trees in the root list will go up, increasing the cost of future dequeue operations.
- 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 2n 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 CS Theory Stack Exchange question and 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 Θ(φn) 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屋！
