斐波那契堆被证明是很难理解的——尽管CLR已经使
很好的尝试让它理解它是如何工作的但有些问题
我真的不清楚：
为什么要选择像t+2m这样的势函数？理由是什么？
标记节点背后的原因是什么-我认为
根列表中的节点等，但为什么要提出这样的方案？
谢谢！
最佳答案
选择势函数的原因与不同因素的组合有关。通常，电位选择为t+2m，其中t是树的数目，m是标记节点的数目我们可以分别分析这些片段。
首先，潜在函数包含一个t项，因为delete min步骤通过重复合并链表中的不同树来工作。执行此操作所需的时间取决于有多少棵树，每次迭代都会将树的数量减少到大约o（log n）的数量，其中n是堆中的节点数量。通过使潜在的函数包含一个t项，可以将折叠所有树的工作反向收费给先前的操作，这些操作首先将树添加到此列表中。
出于类似的原因，势函数包含一个2百万的项当我们调用decrease key时，我们从其父节点中剪切节点，然后标记父节点如果父对象已经标记，我们将其剪切，然后也标记其父对象。这里所做的工作量与我们切割节点时所走路径的长度成正比，但随后它会取消标记所有涉及的节点。因此，如果我们有一个潜在的函数来考虑标记节点的数量，那么我们可以说，虽然单个长序列的削减可能是昂贵的，但是这项工作可以由早期的操作来承担，并且分布得更均匀。这个项是2m而不是m的原因是，当我们通过减少被切断的节点数量来降低电位时，我们也通过在链表中添加更多的树来增加t电位。通过说一个有标记的节点中的每一个下降将电位降低两个，那么从一个下降中的电位的净下降是-1，因此我们可以将一个未来的合并步骤充电到这个下降。
至于为什么我们要做标记-这主要是为了在确定可以保留在斐波纳契堆中的树的数量和大小时，使数学计算得到正确的结果。有人可以说，这是真正的天才步骤，需要提出斐波纳契堆在第一位。从本质上讲，如果你能从每棵树上切下太多的子级，那么堆就失去了平衡，如果你不能切得足够多，那么你就不能有效地实现reduce key。找到“你可以失去一个孩子”这句话的平衡点是一个很好的折衷方案，并能很好地计算出结果。
希望这有帮助！