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

Question

我是从“算法简介”开始学习 f-heap 的，而“减少键”操作真的让我很困惑——为什么这需要“级联切割”？

如果这个操作被移除:

1. make-heap()、insert()、minimum()和union()的成本明显保持不变
2. extract-min() 仍然是 O(D(n))，因为在 O(n(H)) 的“合并”操作中，大多数有根树的成本可以在它们被添加到时支付根列表，剩余成本O(D(n))
3. decrease-key():显然是 O(1)

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

为我糟糕的英语道歉:(

有人可以帮忙吗？谢谢

Answer 1

级联切割的原因是保持 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)。

希望这对您有所帮助!