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

Question

我正在学习《算法导论》中的f堆，并且“减小关键字（decrease-key）”操作确实让我困惑-为什么需要“级联砍枝”？

如果去掉此操作：

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

至于D(n)，尽管我无法精确解释，但我认为它仍然是O(lgn)，因为没有“级联砍枝”，一个节点可能稍后才会移动到根列表中，任何隐藏在其父节点下面的节点都不会影响效率。至少，这不会使情况更糟。

很抱歉我的英语不好:(

有人能帮忙吗？ 谢谢

- exprosic

---

很棒的问题。仅仅抛弃掉父级位置中的所有信息似乎非常不直观。 - Thomas Ahle

Answer 1

进行级联裁剪的原因是为了保持D（n）的低水平。如果您允许从一棵树中剪切任意数量的节点，则D（n）可能增长到线性，这使得删除和删除最小值需要线性时间。

直观来看，您希望k阶树中的节点数呈指数增长。这样，您就可以仅在一个合并堆中拥有对数多个树。如果您可以从一棵树中剪切任意数量的节点，则会失去此保证。具体而言，您可以取一棵k阶树，然后将其所有孙子节点都剪掉。这留下了一棵有k个子节点的树，每个子节点都是叶子节点。因此，您可以用仅具有k + 1个总节点的树创建k阶树。这意味着在最坏的情况下，您需要一棵（n-1）阶树来保存所有节点，因此D（n）变成了n-1，而不是O（log n）。

希望这能帮助您！

- templatetypedef

---

是的，你说得对。这个误导性的D(n)确实会引起问题，但当提取D(n)子节点的父节点时（我写的原因在上面），这个问题并不会出现。它出现在“合并”期间，即它们的父节点选择其父节点时--错误的D()会导致不平衡。现在考虑一下，如果在使用cas-cut减少键值后，我可以像之前进行cas-cut那样维护所有的D(n)，也就是说，D()可能比子节点数量小--extract-min的复杂度仍然是O(lgn)。要精确地维护相同的D()很难，但我认为还有另一种方法来保持平衡： - exprosic

每个节点都有一个S：最初，它是节点的大小。显然，它是2的幂次方--在二进制表示中，为10..000。当其孩子被移除时，其位数（[log2(S)]）会减少（1000->111，1011->101等），它会将差异报告给其父级。当差异足够大以降低父级的[log2(s)]时，差异会报告给祖父母，以此类推。 - exprosic

相同的重点是隐藏节点数量对父节点的减少，但保持S（或D）与节点的实际数量之间的关系（具有S个节点的树至少有S/2个节点），并在O（1）时间内，在合并期间使用S/D来保持平衡（将具有相同D或相同[log2（S）]的节点组合）。这样对吗？ - exprosic

修复：在注释1中：通过cas-cut减少一个键后 -> 在减少一个键时不使用cas-cut（我的非cas-cut斐波那契堆中的所有D()字段都像使用cas-cut-fib-heap一样维护）。 - exprosic

@exprosic- 我认为这里有两个不同的问题。第一个问题 - Fibonacci堆为什么要进行级联剪切？- 我在上面已经尝试回答了。你的第二个问题 - 我们能用另一种方式吗？- 是一个非常有趣的问题，但我认为它可能不是最适合在Stack Overflow上讨论的。你可能想要在cs.stackexchange.com或cstheory.stackexchange.com上详细描述你的方法，以便更多专业的计算机科学家可以审查它。 - templatetypedef