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