algorithm - 斐波那契堆上每个操作的最坏情况时间界限是多少？

Question

斐波那契堆在摊销意义上是有效的，但在最坏的情况下它们的效率如何？具体来说，在 n 节点斐波那契堆上，每个操作的最坏情况时间复杂度是多少？

• 找到最小值
• 删除分钟
• 插入
• 减少键
• 合并

Answer 1

Fibonacci 堆上的 find-min 操作总是需要最坏情况的 O(1) 时间。总是有一个指针直接指向该对象。

在最坏的情况下，删除分钟的成本需要时间 Θ(n)。要看到这一点，想象一下从一个空堆开始并对其进行一系列 n 插入。每个节点都将存储在自己的树中，并且执行 delete-min 堆会将所有这些对象合并为 O(log n) 树，需要 Θ(n) 工作来访问所有节点至少一次。

插入的成本是最坏情况 O(1)；这只是创建一个节点并将其添加到列表中。合并同样是 O(1)，因为它只是将两个列表拼接在一起。

在最坏情况下减少键的成本是 Θ(n)。可以构建一个退化的斐波那契堆，其中所有元素都存储在由 n 个标记节点的链表组成的单个树中。在最底部的节点上执行减少键然后触发一系列级联切割，将树转换为 n 个独立节点。