问题标签 [fibonacci-heap]

我已经阅读了关于 Fibonacci heaps 的 Wikipedia 文章并阅读了 CLRS 对数据结构的描述，但它们对这种数据结构的工作原理提供了很少的直觉。为什么斐波那契堆的设计方式是这样的？它们是如何工作的？

谢谢！

如何在斐波那契堆上的递减键操作中获得 O(1) 摊销复杂度？仅使用 BFS 在斐波那契堆中找到包含该元素的节点需要 O(n) 时间，这应该使得不可能获得 O(1) 摊销时间。

作为参考，这是我搜索相关节点的 BFS 实现：

这是我的减少键代码：

我读到斐波那契堆保留一个全局节点计数器，但我不明白为什么。我什至找到了一个有计数器但根本没有使用它的实现。

我正在使用 Fibonacci heap(boost) 对元素数组进行排序，但我无法遍历堆。代码是这样的：

它在“elem = *it”行给了我这个错误：recursive_tree_iterator 实例化错误：recursive_tree_iterator(void): adapter_type(0) {}

有没有办法做到这一点？或者使用另一个有序堆而不是斐波那契？非常感谢。

extract-min在n-element Fibonacci heap上执行的实际最长时间是多少？

是， n 元素堆中节点的最大度数在O(D(n) + t(H))哪里，堆 H 中的根数是多少？D(n) = lg*nt(H) = O(n)

这是否意味着上述问题的答案实际上是O(n) = Theta(n)？如果不是，请纠正我的想法并回答。

我在查看 boost Fibonacci 堆的代码，在很多地方，我看到一个名为_idof type的变量ID（模板的一部分）被这样使用：get(_id, d)， where dis of type T&， whereT是模板的一部分。这样做的目的是什么，以及仅使用默认的 c++ 标准库的等价物是什么。

这是斐波那契堆的代码：

我正在实现快速行进算法，这是某种连续的 Dijkstra。正如我在许多论文中所读到的，斐波那契堆是最适合此目的的堆。

但是，当使用 callgrind 分析我的代码时，我看到以下函数占用了 58% 的执行时间：

具体来说，pop()它占用了整个执行时间的 57.67%。

heap_定义如下：

花费“那么多”时间是否正常，或者我可以做些什么来提高性能？

抱歉，如果没有提供足够的信息。我尽量简短。如果需要，我会添加更多信息。

谢谢！

我现在这是一个被问过很多次的问题。但是，我找不到针对我的具体问题的解决方案。

我已经在 C++11 和两个不同的变体中实现了快速行进方法（非常类似于 Dijkstra）：斐波那契堆和二进制堆。为此，我使用了 Boost 1.55 堆实现（Fibonacci 和 D_ary，D=2）。

预计二进制堆在小型网格中更快，而斐波那契在大型网格中更快。但是，二叉堆总是更快（并且存在“巨大”差异）。例如：

我-Ofast -fno-finite-math-only在 G++ 4.8 中使用标志。

要点是我可以保证几周前完全相同的实现返回了预期的结果。

有人可以给我一些启示吗？

谢谢！

我正在阅读CLRS并遇到了一行“斐波那契堆延迟尽可能长的工作”。但是延迟工作实际上意味着什么，以及这与性能有何关系。

我试图了解如何实现斐波那契堆操作。鉴于我们有以下堆：

例如，我们如何将 35 减少到 27？由于 27 不大于 30，因此没有保留顺序，因此我们必须重建堆。那么27去哪儿了？5岁以下？