问题标签 [fibonacci-heap]

在了解了斐波那契堆及其操作（MAKE_HEAP、MIN、INSERT、UNION、EXTRACT_MIN、DELETE ..）后，我遇到了一个问题，我无法理解如何证明每个 h>=0 都有应用于初始堆的斐波那契堆操作会在下面的图 2-a 中产生一个堆。此外，我们如何证明对于每个 h>=0 存在应用于初始堆的斐波那契堆操作会导致以下 fgure 2-b 中的堆：

任何帮助或提示将不胜感激。

让我们假设在执行操作（make heap、min、insert、union、extract min）之后获得了 n 节点斐波那契堆。我们如何估计树的数量、度数 k>= 0 的树的大小以及生成的斐波那契堆中节点的最大度数？另外，假设插入和联合操作包括最后阶段的合并过程，我们如何估计前一个。任何提示或帮助将不胜感激。

我想实现一个严格的斐波那契堆，但结构非常复杂，如果有任何语言的示例实现会很好。但是我还没有找到。

似乎 2012 年的论文“Strict Fibonacci Heaps”是唯一详细描述这种结构的来源。但是在“优先队列的回归基础实证研究”中，他们测量了它的实际性能，因此他们必须实现堆。

是否有任何公开可用的实现？

我正在尝试使用潜在方法对斐波那契堆进行摊销分析。我正在努力理解对 pop min / delete min 操作的分析。

在教程中，我可以找到限制“pop min”操作的摊销复杂度，例如这个，教程作者将潜力设置为“phi(fib heap) = 根节点数 + 2 * 失败节点数”。然后他们分两个步骤分析 popmin 操作：

1. 第一步，它删除最小节点并将最小节点的子节点放在根列表中。通过对树的分析（不允许任何节点失去一个以上的孩子这一事实），您知道这将只需要 O(log n) 次操作。这部分我明白了。

2. 在第二步中，您通过迭代合并所有相同大小的树来执行清理。对我来说，这就是分析变得令人困惑的地方：

在摊销分析中，成本始终是“实际成本+潜力变化”。他们分析真正的成本为 O(t + m + d)——m 为合并的次数，d 为合并后的树数，而 t 为合并前的节点数当您对根列表进行线性扫描时进行清理。上面的电位变化受 -m 的约束——根列表的大小随着合并次数的增加而减小。t = m + d，所以操作是 O(m + d)。到目前为止，我正在关注。

然后，在链接的教程中，他将电位变化添加到 O(m + d) 以得到 O(m + d) - m = O(d) ...这没有任何意义！我相当肯定，根据大 O 的定义，这是不可能的。尽管如此，这仍然是他在视频中为 popmin 操作摊销成本的理由。

任何人都可以用 O(m + d) - m 来解释他的意思，或者如果没有，可以用一种分析斐波那契堆中的 popmin 操作以获得 O(log n) 的摊销运行时间的方法吗？