问题标签 [fibonacci-heap]

你们有没有人实现过Fibonacci-Heap？几年前我就这样做了，但它比使用基于数组的 BinHeaps 慢了几个数量级。

那时，我认为这是一个宝贵的教训，说明研究并不总是像它声称的那样好。然而，许多研究论文声称他们的算法的运行时间基于使用斐波那契堆。

你有没有设法产生一个有效的实施？或者您是否使用过大到斐波那契堆效率更高的数据集？如果是这样，一些细节将不胜感激。

我已经在 J​​ava 中研究斐波那契堆实现大约一周了。它是基于 CLRS 书的实现。

我想看看与 Java 的默认 PriorityQueue 相比，在我正在处理的副项目中使用它是否会获得任何性能提升。[Java 中的默认实现是基于数组的，因此更加本地化。尽管复杂度更高，但它仍可能优于 F-Heap]。

我的问题似乎源于删除 min 元素后堆的合并部分。我不断收到 arrayindexoutofboundsexceptions 抛出。特别是在while循环中，当它合并具有相同度数的所有节点时。它超出了 D() 函数设置的范围。

所以要么我的 D() 函数是错误的，我不认为它是错误的，要么是发生了其他事情。最有可能与副作用有关。

代码位于此处。我一直在尝试调试这个大约一周，现在很幸运。我错过了一些明显的东西吗？

JGraphT有一个很好的斐波那契堆类。如何使用它来实现Prim 的最小生成树算法？

斐波那契堆和二叉堆的实际应用是什么？如果您可以在使用它来解决问题时分享一些实例，那就太好了。

编辑：还添加了二进制堆。很想知道。

我正在尝试设计一个带有斐波那契堆的 dijkstras 实现。我想了解的是，除了 O(logn) 中的最小距离（带删除）之外，是否可以表示任何给定节点的邻居？或者这是否违反了斐波那契堆结构？否则我将不得不建立一个邻居列表以及一个斐波那契堆。

我知道Prim 的算法，也知道它的实现，但我总是跳过我现在想问的部分。有人写道，Prim 的斐波那契堆算法实现是O(E + V log(V))，我的问题是：

• 简而言之，斐波那契堆是什么？
• 它是如何实施的？和
• 如何用斐波那契堆实现 Prim 算法？

我正在研究不同类型的堆数据结构。

对于 (1) 插入、(2) 删除和 (2) 查找最小元素，斐波那契堆似乎具有更好的最坏情况复杂性。

我发现在 Java 中有一个类PriorityQueue是平衡的二进制堆。但是为什么他们不使用斐波那契堆呢？

另外，是否有斐波那契堆的实现java.util？

谢谢！

我有兴趣实现一个优先级队列以启用一个也相对简单的高效 Astar 实现（我的意思是优先级队列很简单）。

似乎因为跳过列表提供了一个简单的 O(1) 提取最小操作和一个 O(Log N) 的插入操作，它可能与更难实现的具有 O(log N) 提取的斐波那契堆竞争 - Min 和 O(1) 插入。我认为 Skip-List 对于节点稀疏的图会更好，而斐波那契堆对于节点更密集的环境会更好。

这可能会使斐波那契堆通常更好，但我是否正确假设 Big-Oh 明智的这些将是相似的？

是否有任何基于佩尔序列（或佩尔数）而不是斐波那契数（如斐波那契堆）的堆？

在 CLRS 的 Introduction to Algorithms 3rd edition P.525 中，在分析 size(x) 的下界时，我引用了一句话“因为向节点添加子节点不能减小节点的大小，所以 Sk 的值增加与 k 单调”。但实际上，我想我可以举一个反例来说明 Sk 不一定随 k 单调递增。在下图中，key=1的节点度数为2，没有其他度数为2的节点，所以S2=8。同样，S3=6。但现在 S3 小于 S2，这意味着 Sk 根本不随 k 单调增加。

堆可以通过执行一系列切割和级联切割从无序二项式子树派生。

我想知道上述结构是否是有效的斐波那契堆。如果是这样，那么它也是一个有效的反例。