1

我想证明一个具有 n 个节点的斐波那契堆的高度可能为 n。

我用例子试过这个,但我不知道如何展示这个。

4

1 回答 1

25

(我假设您的意思是高度 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。

希望这可以帮助!

于 2013-01-13T03:41:21.427 回答