问题标签 [fibonacci-heap]

Introduction to Algorithms 中的伪代码指出：

但是如何有效地实现每个根节点部分呢？原始根在整个合并过程中与其他相同程度的根相连，很难通过根节点的循环列表。如何确定是否检查了每个根节点？

新来的，但作为客人潜伏了很长一段时间:)

好的，所以我一直在尝试使用斐波那契堆（在 Java 中）做 Dijkstra 的最短路径算法。经过一番搜索，我偶然发现了两个代表斐波那契堆的现成实现。第一个实现做得相当漂亮，可以在这里找到。第二个实现，看起来不那么优雅，在这里。

现在，这一切看起来都很好。但是，我想为我的 Dijkstra 算法版本使用其中一种实现，但我还没有运气。Dijkstra在使用中的实现如下：

很明显，此实现使用基于 Java 的 PriorityQueue 类（我相信它基于二进制堆本身）。我希望修改上面的代码，使其使用上述斐波那契堆实现中的任何一个，而不是 Java 的 PriorityQueue。

我已经尝试了很多，但我就是不知道该怎么做，尽管我确信它就像替换几行代码一样简单。

我希望我足够清楚。这实际上是我在这些板上的第一篇文章。

任何帮助将不胜感激。

编辑：为了回应评论，我想我会用我的尝试场景之一来扩展我的帖子。

这是使用前面链接的第二个斐波那契堆实现的上述 Dijkstra 方法的修改版本：

这几乎是直接从伪代码转换而来的（因此完全有可能我只是没有正确翻译它）。我得到的错误是“decreaseKey() 的值更大”。如果我尝试删除最小值，我会得到 NullPointerException。

我确定我做错了什么，我很想知道它是什么。再次，这是使用第二个 FHeap 实现。我宁愿使用第一个实现来做到这一点（它看起来更彻底/更专业），但不幸的是我不知道如何去做。

我最近使用两种数据结构对 Dijkstra 算法的运行时间进行了初步比较，基于 Java 的 PriorityQueue（如果我没记错的话，基于二进制堆）和 Fibonacci 堆。我使用 Java 的 currentTimeMillis() 进行计算。我最终得到的结果非常有趣。这是我的一个测试用例的输出：

诚然，我目前缺乏数据集，上面的图表是我最大的（我计划尽快制作更多）。但这有意义吗？我一直认为斐波那契堆比其他数据结构更快，因为与其他数据结构相比，它们摊销了运行时间。我不确定这 3 毫秒的差异是从哪里来的。（我在 Intel Core Ivy Bridge i7-3630M 处理器上运行它，如果有帮助的话。）

注意：我偶然发现了这个可能解释这个问题的线程，但我仍然不清楚为什么斐波那契堆版本需要更长的时间。根据该线程，这可能是因为我的图不够密集，因此减少键操作的数量不足以使斐波那契堆的性能真正发挥作用。这是唯一合理的结论，还是我还缺少其他东西？

我正在从“算法简介”中学习 f-heap，而“减键”操作真的让我感到困惑——为什么这需要“级联切割”？

如果删除此操作：

1. make-heap()、insert()、minimum() 和 union() 的成本显然保持不变
2. extract-min() 仍然是 O(D(n))，因为在 O(n(H)) 'consolidate' 操作中，大多数有根树的成本可以在它们被添加到根列表时支付支付，并且剩余成本 O(D(n))
3. 减少键（）：显然O（1）

至于D(n)，虽然我不能准确解释，但我认为它仍然是O(lgn)，因为没有'cascading-cut'，一个节点可能稍后会被移动到根列表，并且任何节点躲在其父之下不影响效率。至少，这不会让情况变得更糟。

为我糟糕的英语道歉:(

有人可以帮忙吗？谢谢

.

嗨，大家好，

我正在使用 Erel Segal 的 C++ STL FibonacciHeap http://ideone.com/9jYnv，我认为它缺少 increase_key() 方法。

我即将自己实现它，但我没有找到很多关于理论实现的参考。

您能给我一些关于如何进行 increase_key 操作的提示吗？

我需要在我的项目中使用斐波那契堆，我正在尝试从 boost 库中使用它。但我无法弄清楚如何为任意数据类型设置用户定义的比较函数。我需要为结构节点构造一个最小堆，定义如下：

我查阅了文档，有一个比较类。但它不包含任何元素。请告诉我如何设置用户定义的比较功能。先感谢您。

Haskell 是否有可用的斐波那契堆/优先级队列？（或者甚至是渐近更好的？）我在这个问题中找到了各种优先级队列实现的列表，但我找不到它们是否满足斐波那契堆的摊销运行时间：

• Find-minimum 是O(1)摊销时间。
• 操作插入、减少键和合并（联合）工作是O(1)摊销时间。
• 操作 delete 和 delete minimum 是O(log n)摊销时间。

参见理论界限的比较。

I have this question when teaching myself Fibonacci Heap, which now I know is an efficient data structure to implement priority queue with amortized O(1) time complexity when decreasing priority of an element in the heap. However, from the CLRS textbook, the priority decreasing operation assumes the node holding target element is pre-known. I'm curious about how could I get the desired node efficiently if not the minimum node. A naive implementation and analysis yields O(n) worst-case time complexity to perform the find operation on a Fibonacci Heap, which is less efficient compared to other operations. So my question is that is there an efficient find operation in Fibonacci Heap, or is it necessary?

我正在使用boost::fibonacci_heapBoost 1.53.0 中的类来维护可更新的优先级队列。

当我想更新一个元素时，我需要将堆中的元素与要替换它的新元素进行比较。我只想用“较小”的版本替换堆中的元素，所以我想在更新之前比较它们。

当我插入元素时，我会存储它们的句柄 ( boost::fibonacci_heap::handle_type)。我在文档中fibonacci_heap看到的所有函数都采用句柄类型，只提供某种写访问（update(),等） decrease()，increase()并且不允许我在更新之前检查句柄标识的元素。

fibonacci_heap有没有办法只使用它的句柄来查看 a 中的元素？

在decrease-key斐波那契堆的操作中，如果允许s > 1在切割节点并将其融合到根列表（提升节点）之前丢失子节点，这是否会改变整体运行时复杂度？我认为复杂性没有变化，因为潜力的变化是一样的。但我不确定我是否正确。

摊销分析如何证明这一点？