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

Question

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

如果删除此操作：

1. make-heap()、insert()、minimum() 和 union() 的成本显然保持不变
2. extract-min() 仍然是 O(D(n))，因为在 O(n(H)) 'consolidate' 操作中，大多数有根树的成本可以在它们被添加到根列表时支付支付，并且剩余成本 O(D(n))
3. 减少键（）：显然O（1）

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

为我糟糕的英语道歉:(

有人可以帮忙吗？谢谢

Answer 1

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

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

希望这可以帮助！