我是从“算法简介”开始学习 f-heap 的，而“减少键”操作真的让我很困惑——为什么这需要“级联切割”？
如果这个操作被移除:
- make-heap()、insert()、minimum()和union()的成本明显保持不变
- extract-min() 仍然是 O(D(n))，因为在 O(n(H)) 的“合并”操作中，大多数有根树的成本可以在它们被添加到时支付根列表，剩余成本O(D(n))
- decrease-key():显然是 O(1)
至于D(n)，虽然我无法准确解释，但我认为它仍然是O(lgn)，因为没有'cascading-cut'，一个节点可能只是移动到根列表a稍后，任何节点隐藏在其父亲之下不影响效率。至少，这不会使情况变得更糟。
为我糟糕的英语道歉:(
有人可以帮忙吗？ 谢谢
最佳答案
级联切割的原因是保持 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/