事实证明，斐波那契堆很难理解——尽管 CLRS 已经做出了很好的尝试来让它理解它是如何工作的。但有些问题我真的不清楚：
- 为什么要选择像 t + 2m 这样的势函数？原因是什么？
- 节点标记背后的原因是什么 - 我看到将节点放在根列表等中很有用，但你为什么要提出这样的方案？
谢谢！
问问题
973 次
1 回答
4
选择势函数的原因与不同因素的组合有关。通常情况下，潜力选择为 t + 2m，其中 t 是树的数量，m 是标记节点的数量。我们可以分别分析这些片段。
首先，势函数包括 at term，因为 delete-min 步骤通过重复将链表中的不同树合并在一起来工作。执行此操作所需的时间取决于有多少棵树，并且每次迭代都会将树的数量减少到大约 O(log n) 的数字，其中 n 是堆中的节点数。通过在术语中包含潜在功能，折叠所有树所做的工作可以回退到最初将树添加到此列表中的早期操作。
出于类似的原因，势函数包括一个 2m 项。当我们调用 reduce-key 时，我们将节点从其父节点中删除，然后标记父节点。如果已经标记了父级，我们将其剪切，然后也标记其父级。此处完成的工作量与我们在不断切割节点时所采用的路径长度成正比，但随后它会取消标记所有涉及的节点。因此，如果我们有一个将标记节点的数量考虑在内的潜在函数，那么我们可以说，虽然单个长系列的削减可能很昂贵，但这项工作可以退回到早期的操作中并更均匀地分布。这个项是 2m 而不是 m 的原因是，当我们通过减少被切割节点的数量来降低潜力时，我们也通过将更多的树重新添加到链表中来增加 t 潜力。
至于我们为什么要做标记 - 这主要是为了在确定可以保留在斐波那契堆中的树的数量和大小时正确计算数学。可以说，这是首先提出斐波那契堆所需的真正天才步骤。本质上，如果你可以从每棵树上切割太多的孩子，那么堆就会失去平衡，如果你不能切割得足够多，那么你就不能有效地实现 reduce-key。在说“你可能会失去一个孩子”之间找到平衡是一个很好的折衷方案，并且可以使得出的数学结果非常好。
希望这可以帮助！
于 2012-01-31T21:48:12.630 回答