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

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',一个节点可能稍后被移动到根列表,并且任何节点隐藏在父亲之下不会影响效率.至少,这不会使情况变得更糟.

为我可怜的英语道歉:(

谁有人可以帮忙？谢谢

Answer 1

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

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

希望这可以帮助!