如何获得斐波那契堆的最坏情况
什么操作顺序会给出斐波那契堆的最坏情况？除了最后一个节点之外，每个节点只有一个子节点？
例如：
5
|
6
|
7
|
8
What sequence of operations would give the worst case for fibonacci heaps? Where each node has only one child except for the last node?
For example:
5
|
6
|
7
|
8
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
我认为 jpalecek 的答案不会产生所请求的树。在这里尝试一下：
http://www.cse.yorku.ca/~ aaw/Jason/FibonacciHeapAnimation.html
此外，您只需插入任意数量的元素，然后 extract-min 一次即可获得相同的结果。无论如何，这不是要求。
要实现您想要的形式，请执行以下操作：
-inf除了最左边的，从最深，从左到右（参见下面的演示）。示例：
7减少到0：5减少到0，提取 min ，将4减少到0，提取 min ，减少3至0，提取 min ，将10减少到0，提取 min:编辑：
我忘记了有一个
删除操作可以使减少然后提取分钟，所以你可以使用它来代替减少然后提取分钟我在上面所做的。请注意，现在当您有一个“单路径”树时，您可以通过以下 O(1) 操作序列轻松地继续扩大它：
演示（继续示例的最后一步）：
1，0，-1：1):所有图像均由此网站
I think jpalecek's answer doesn't produce the requested tree. Try it here:
http://www.cse.yorku.ca/~aaw/Jason/FibonacciHeapAnimation.html
Also, You can achieve the same result just by inserting whatever number of elements and then extract-min once. Anyway, that's not the request.
To achieve the form you wanted do this:
-infexcept the leftmost, starting from the deepest, and from left to right (see demonstration below).example:
7to0:5to0, extract min , decrease4to0, extract min , decrease3to0, extract min , decrease10to0, extract min:edit:
I forgot there's a
deleteoperation that makesdecreasethenextract min, so you can use it instead of the decrease then extract min i was doing above.And note that now when you have a "single path" tree, you can easily keep enlarging it by this sequence of O(1) operations:
demonstration (continuing last step from the example):
1,0,-1:1):all images are created by this website
这实际上是最好的情况（如您所见， extract-min 总是很容易，因为我们已经对元素进行了排序）。您应该通过以下方式插入一系列反向排序的元素（即最小元素排在最后）来获取它：
This is actually the best case (as you can see, extract-min is always easy, since we have the element ordered). You should get it by inserting a sequence of reverse-sorted elements (that is, the minimal element would come last) in this manner: