algorithm - 如何获得斐波那契堆的最坏情况

Question

什么样的操作顺序会给出斐波那契堆的最坏情况？除了最后一个节点，每个节点只有一个 child ？

例如:

5
|
6
|
7
|
8

Answer 1

我认为 jpalecek 的回答没有生成请求的树。在这里试试:

http://www.cse.yorku.ca/~aaw/Jason/FibonacciHeapAnimation.html

此外，您只需插入任意数量的元素然后提取一次即可获得相同的结果。无论如何，这不是要求。

要实现您想要的形式，请执行以下操作:

• 插入任意数量的元素 - 例如 1 到 10。
• 提取最小值(现在你只有一棵树)
• 将所有 child 减少到 -inf 除了最左边，从最深的开始，从左到右(见下面的演示)。
• 每次减少后，删除min
• 重复第 3 步

示例:

• 插入 1 到 10:

• 提取分钟:

• 将 7 减少到 0:

• 提取分钟:

• 将 5 减少到 0，提取 min ，将 4 减少到 0，提取 min ，减少 3 到 0，提取 min ，将 10 减少到 0，提取 min:

编辑:

我忘了有一个delete 操作使decrease 然后extract min，所以你可以用它代替decrease then提取分钟我在上面做的。

请注意，现在当您拥有一个“单路径”树时，您可以通过以下 O(1) 操作序列轻松地继续扩大它:

• 插入 3 个小于 min 的元素
• 提取分钟
• 删除新的右 child

演示(继续示例的最后一步):

• 插入1,0,-1:

• 提取分钟:

• 删除新的右 child (1):

所有图像均由 this website 创建