我想证明一个具有 n 个节点的斐波那契堆的高度可能为 n。
我用例子试过这个,但我不知道如何展示这个。
(我假设您的意思是高度 n - 1:高度 n 是不可能的,因为对于 n 个节点,最大高度是高度 n - 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。
希望这可以帮助!