algorithm - 如何显示具有 n 个节点的斐波那契堆可以有高度 n？

Question

我想证明一个具有 n 个节点的斐波那契堆的高度可能为 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

如果您重复执行添加三个节点、删除一个节点、然后删除剩下的单个树的单个子节点的过程，您可以使斐波那契堆成为高度为 n - 1 的单个树，用于您想要的任何 n。

希望这可以帮助！