问题描述
我想显示一个具有n个节点的斐波纳契堆可能具有高度n。
I want to show that a Fibonacci heap with n nodes could have height n.
我尝试了这个例子，但我不知道如何显示这个
I tried this with examples but I don't know how to show this in general.
推荐答案
（我假设你的意思是高度n - 1：高度n是不可能的，因为n个节点的最大高度是高度的链接列表n - 1）
(I assume you mean height n - 1: height n is impossible since with n nodes the maximum height is a linked list of height n - 1)
获取高度一个很容易：添加三个节点，然后执行一个出队最小值。这将删除一个节点，并将高度为0的其他两个节点组合到高度为1的结构中：
Getting to height one is easy: add in three nodes, then do a dequeue-min. This removes one node and combines the other two nodes, which have height 0, into this structure of height 1:
A
|
B
如果您再次重复此过程，并确保其中一个新节点最低优先，你得到这两棵树，然后将它们合并在一起，如下所示：
If you repeat this process again and ensure one of the new nodes has the lowest priority, you get two of these trees, which are then merged together like this:
A
|\
B C
|
D
现在，在B上执行删除操作。一个标记：
Now, do a delete operation on B. This leaves A with order 1 and a mark:
A*
|
C
|
D
重复此过程（插入三个节点，所有这些节点都具有无限的负优先级，并调用dequeue-min）来获得这一点：
Repeat this process again (insert three nodes, all of which have infinite negative priority, and call dequeue-min) to get this:
E
|\
F A*
|
C
|
D
删除F以获取
E*
|
A*
|
C
|
D
如果您反复执行此过程添加三个节点，删除一个，然后删除单个剩下的树的单身孩子，你可以使斐波那契堆成一个单一的高度n - 1的树，任何你想要的。
If you repeatedly execute this process of adding three nodes, deleting one, then deleting the singleton child of the single remaining tree, you can make the Fibonacci heap a single tree of height n - 1 for any n you'd like.
希望这有帮助！
这篇关于如何显示具有n个节点的斐波那契堆可以具有高度n？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！