algorithm - 为什么斐波那契堆需要级联切割？

我正在从“算法介绍”中学习 f-heap，而“减少键”操作真的让我感到困惑——为什么这需要“级联切割”？

如果删除此操作:

make-heap(), insert(), minimum() 和 union() 的开销明显保持不变

extract-min() 仍然是 O(D(n))，因为在 O(n(H)) 'consolidate' 操作中，大多数有根树的成本可以支付 添加到根列表 0x21234119 , 剩余成本 O(D(n))

减少键():显然是 O(1)

至于 D(n)，虽然我无法准确解释，但我认为它仍然是 O(lgn)，因为没有 'cascading-cut'，节点 可能会在稍后移动到根列表 ，并且任何节点 隐藏在其父节点 下都不会影响效率。至少，这不会让情况变得更糟。

为我糟糕的英语道歉:(

任何人都可以帮忙吗？
谢谢

最佳答案

级联切割的原因是保持 D(n) 低。事实证明，如果允许从树中切割任意数量的节点，则 D(n) 可以增长为线性，这使得 delete 和 delete-min 花费线性时间。

直观地说，您希望 k 阶树中的节点数是 k 的指数。这样，您只能在合并的堆中拥有对数数量的树。如果您可以从树中剪切任意数量的节点，您就失去了这种保证。具体来说，您可以取一棵 k 阶树，然后砍掉它的所有孙子树。这留下一棵树有 k 个 child ，每个 child 都是叶子。因此，您可以创建 k 阶树，其中只有 k + 1 个节点。这意味着在最坏的情况下，您需要一棵 n - 1 阶的树来保存所有节点，因此 D(n) 变为 n - 1 而不是 O(log n)。

希望这可以帮助!

关于algorithm - 为什么斐波那契堆需要级联切割？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/15940984/