如何显示具有n个节点的斐波那契堆可以具有高度n？ [英] How to show Fibonacci heap with n nodes can have height n?

问题描述

我想显示一个具有n个节点的斐波纳契堆可能具有高度n。

I want to show that a Fibonacci heap with n nodes could have height n.

我尝试了这个例子，但我不知道如何显示这个

I tried this with examples but I don't know how to show this in general.

推荐答案

（我假设你的意思是高度n - 1：高度n是不可能的，因为n个节点的最大高度是高度的链接列表n - 1）

(I assume you mean height n - 1: height n is impossible since with n nodes the maximum height is a linked list of height n - 1)

获取高度一个很容易：添加三个节点，然后执行一个出队最小值。这将删除一个节点，并将高度为0的其他两个节点组合到高度为1的结构中：

Getting to height one is easy: add in three nodes, then do a dequeue-min. This removes one node and combines the other two nodes, which have height 0, into this structure of height 1:

A
|
B

如果您再次重复此过程，并确保其中一个新节点最低优先，你得到这两棵树，然后将它们合并在一起，如下所示：

If you repeat this process again and ensure one of the new nodes has the lowest priority, you get two of these trees, which are then merged together like this:

A
|\
B C
  |
  D

现在，在B上执行删除操作。一个标记：

Now, do a delete operation on B. This leaves A with order 1 and a mark:

A*
|
C
|
D

重复此过程（插入三个节点，所有这些节点都具有无限的负优先级，并调用dequeue-min）来获得这一点：

Repeat this process again (insert three nodes, all of which have infinite negative priority, and call dequeue-min) to get this:

E
|\
F A*
  |
  C
  |
  D

删除F以获取

E*
|
A*
|
C
|
D

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

If you repeatedly execute this process of adding three nodes, deleting one, then deleting the singleton child of the single remaining tree, you can make the Fibonacci heap a single tree of height n - 1 for any n you'd like.

希望这有帮助！

这篇关于如何显示具有n个节点的斐波那契堆可以具有高度n？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！