斐波那契堆在摊销意义上是有效的，但在最坏的情况下它们的效率如何？具体来说，在 n 节点斐波那契堆上，这些操作中的每一个的最坏情况时间复杂度是多少？
- 查找最小值
- 删除分钟数
- 插入
- 减键
- 合并
斐波那契堆上的查找最小值操作总是需要最坏情况下的 O(1( 时间。始终维护一个直接指向该对象的指针。
在最坏的情况下，删除分钟的成本需要时间 Θ(n(。要看到这一点，请想象从一个空堆开始，然后在其中执行一系列 n 次插入。每个节点将存储在自己的树中，并且执行 delete-min 堆会将所有这些对象合并到 O(log n( 树中，需要 Θ(n( 工作至少访问所有节点一次。
插入的成本是最坏情况 O(1(;这只是创建一个节点并将其添加到列表中。合并类似于 O(1(，因为它只是将两个列表拼接在一起。
在最坏的情况下，减法键的成本为 Θ(n(。可以构建一个退化的斐波那契堆，其中所有元素都存储在由 n 个标记节点的链表组成的单个树中。在最底部的节点上执行递减键会触发一系列级联切割，将树转换为 n 个独立的节点。
我几乎同意@templatetypedef的伟大答案。
不能有带有 $n$ 标记节点的经典斐波那契堆树。这意味着树的高度是 O(n(，但由于对于每个等级为 $k$ 的子树，它的子树的秩为 $\geq 0， \geq 1， ...， \geq k-1$。很容易看出，树的深度最多是O(logn(。因此，单个减键操作可能会花费 O(logn(。
我检查了这个线程，它需要对斐波那契堆进行一些修改，因为它在根列表中标记了节点并执行了不属于斐波那契堆的操作。