斐波那契堆中的所有树都是二项式树吗？
斐波那契堆是否可能包含一棵不是二项式树的树？如果是这样，怎么会发生这种情况呢？你能举个例子吗？
Is it possible for a Fibonacci heap to contain a tree that isn't a binomial tree? If so, how would this happen? Can you give an example?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
是的，这可能会发生。直观上，原因是在斐波那契堆中，减少键操作可以通过从较大的树中剪切子树来进行，从而产生两棵（可能）不是二项式树的树。这与二项式堆不同，在二项式堆中，减少键的工作原理是从键被减少的节点一直到根进行冒泡操作。
看一个具体的例子，让我们向斐波那契堆中插入 5 个元素，例如 1、3、5、7 和 9。这给出了堆。
现在，让我们执行一个 dequeue-min，提取 1。我们现在尝试压缩将所有剩余元素合并在一起，如下合并树：
现在，假设我们执行减少键操作，将 9 的键减少到 6。为此，我们从其父级中删除 9并将其合并到顶部的树列表中，生成
现在根为 3 的树仅包含 3 个元素，因此它不再是二项式树。
希望这有帮助！
Yes, this can happen. Intuitively, the reason is that in a Fibonacci heap, the decrease-key operation can work by cutting a subtree from a larger tree, resulting in two trees that are (potentially) not binomial trees. This differs from the binomial heap, where decrease-key works by doing a bubble-up operation from the node whose key was decreased all the way up to the root.
To see a concrete example, let's insert five elements into a Fibonacci heap, say, 1, 3, 5, 7, and 9. This gives the heap
Now, let's do a dequeue-min, which extracts 1. We now try to compact all of the remaining elements together, which merges the trees as follows:
Now, suppose that we do a decrease-key operation on to decrease the key of 9 to 6. To do this, we cut 9 from its parent and merge it into the list of trees at the top, which yields
And now the tree with 3 at its root contains only 3 elements, so it is not a binomial tree anymore.
Hope this helps!