如何显示具有n个节点的Fibonacci堆可以具有高度n？

Question

我想证明具有n个节点的Fibonacci堆可以具有高度n.

我用例子尝试了这个,但我不知道如何在一般情况下显示这个.

Answer 1

(我假设你的意思是身高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

如果您反复执行添加三个节点的过程,删除一个节点,然后删除单个剩余树的单个子节点,则可以使Fibonacci堆为任何您想要的n的单个高度为n - 1的树.

希望这可以帮助!