algorithm - 关于斐波那契堆的设计与分析的问题

Question

Fibonacci 堆被证明很难理解 - 尽管 CLRS 已经让它理解它是如何工作的非常好的尝试。但有些问题我真的不清楚:

• 您为什么会选择像 t + 2m 这样的势函数？原因是什么？
• 节点标记背后的原因是什么 - 我看到它很有用根列表中的节点等，但你为什么会想出这样的方案？

谢谢!

Answer 1

选择潜在函数的原因与不同因素的组合有关。通常，潜力选择为 t + 2m，其中 t 是树的数量，m 是标记节点的数量。我们可以分别分析这些片段。

首先，势函数包含一个 t 项，因为 delete-min 步骤的工作原理是将链表中的不同树反复合并在一起。执行此操作所需的时间取决于有多少棵树，每次迭代都会将树的数量减少到一个大致为 O(log n) 的数字，其中 n 是堆中的节点数。通过使潜在函数包含一个 t 项，折叠所有树所做的工作可以回馈到最初将树添加到此列表中的早期操作。

出于类似原因，势函数包含一个 2m 项。当我们调用 decrease-key 时，我们从它的父节点切下节点，然后标记父节点。如果父级已经被标记，我们将其剪切，然后也标记其父级。此处完成的工作量与我们在不断切割节点时所采用的路径长度成正比，但随后它取消标记所有涉及的节点。因此，如果我们有一个潜在的函数将标记节点的数量考虑在内，那么我们可以说虽然单个长系列的切割可能很昂贵，但该工作可以回馈到较早的操作并更均匀地分布。此项为 2m 而不是 m 的原因是，当我们通过减少被切割的节点数量来降低潜力时，我们还通过将更多树添加回链表来增加 t 潜力。通过说标记节点中的每个下降将势能减少两倍，切割的势能净下降为 -1，因此我们可以将 future 的合并步骤计入此减少。

至于我们为什么要进行标记 - 这主要是为了在确定斐波那契堆中可以保留的树的数量和大小时让数学计算正确。人们可以争辩说，这是首先提出斐波那契堆所需的真正天才步骤。本质上，如果你可以从每棵树上切下太多的 child ，那么堆就会失去平衡，如果你不能切得足够多，那么你就不能有效地实现 decrease-key。找到说“你可以失去一个 child ”的平衡点是一个很好的折衷方案，并且可以很好地得出结果。

希望这对您有所帮助!