<分区>
我想证明具有 n 个节点的斐波那契堆的高度可能为 n。
我用例子试过了，但我不知道如何一般地展示这一点。
<分区>
我想证明具有 n 个节点的斐波那契堆的高度可能为 n。
我用例子试过了，但我不知道如何一般地展示这一点。
最佳答案
(我假设你的意思是高度 n - 1:高度 n 是不可能的，因为对于 n 个节点，最大高度是高度 n - 1 的链表)
达到高度 1 很容易:添加三个节点，然后执行 dequeue-min。这将删除一个节点并将高度为 0 的其他两个节点合并到这个高度为 1 的结构中:
A
|
B
如果您再次重复此过程并确保其中一个新节点具有最低优先级，您将获得其中两棵树，然后将它们合并在一起，如下所示:
A
|\
B C
|
D
现在，对 B 执行删除操作。这会为 A 留下订单 1 和一个标记:
A*
|
C
|
D
再次重复这个过程(插入三个节点，所有节点都具有无限负优先级，并调用dequeue-min)得到这个:
E
|\
F A*
|
C
|
D
删除F得到
E*
|
A*
|
C
|
D
如果您重复执行添加三个节点、删除一个节点，然后删除剩下的单个树的单个子节点的过程，您可以使斐波那契堆成为一棵高度为 n - 1 的树，对于任何您想要的 n。
希望这对您有所帮助!
关于algorithm - 如何显示具有 n 个节点的 Fibonacci 堆可以有高度 n？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/14300256/