问题标签 [fibonacci-heap]

我知道 Prim 的算法以及如何实现它。我也知道为什么它的时间复杂度是 O(E + V log(V))。

我们添加边 E 次（即 O(E)）并选择最小 V 次（即 O(V*log(V)）。但我不明白其中的一部分：为什么 V 次？！我知道一棵树有 V-1 条边，但如果最重的边必须在 MST 中，我们必须选择最少 E 次，而不是 V 次。

例如：一个完整​​的图，每条边的权重为 1，除了一个顶点，所有连接到它的边的权重为 10^18。

我正在寻找MST的线性时间复杂度。我正在尝试使用斐波那契堆作为其联合来进行此操作，并发现最小操作需要恒定的时间。是否有任何链接可以降低 MST 的时间复杂度？请帮忙。

我现在正在根据Fredman 和 Tarjan的原始论文实现斐波那契堆。如果我理解正确，根据论文，要执行节点x的DecreseKey操作，我们只需将其从其父节点中删除即可。但是如果减少后的键仍然大于其父键，那将是低效的（我认为）。此外，我看到许多设计仅在节点的密钥变得小于其父节点时才切断节点，例如在 CLRS 中。

所以我对它的原始设计有点困惑。他们为什么不采用更有效的方法来做DecreaseKey。或者也许它使摊销分析更容易？任何回应表示赞赏。提前致谢。

Boost 文档和以前的堆栈溢出都提供了如何定义自定义比较器函数的工作示例，并在 boost 堆的节点类型中包含句柄。但是，当我结合这两个功能（自定义定义的比较函数和节点类型中的句柄）时，我收到错误报告，报告无效使用不完整类型的“struct compare_Node”。

https://www.boost.org/doc/libs/1_63_0/doc/html/heap/concepts.html#heap.concepts.mutability

使用 boost fibonacci_heap

在 boost 中为斐波那契堆定义比较函数

减少斐波那契堆中的操作，提升

除了预定义 Node 和 compare_Node 的两个结构之外，我不确定在仍将句柄作为 Node 结构中的成员安全地持有的同时解决循环问题。

我一直在尝试实现堆数据结构以用于我的研究工作。作为其中的一部分，我正在尝试为最小堆实现增加键操作。我知道最小堆通常支持减少键。我能够为二进制最小堆编写增加密钥操作，其中，我递归地与最小的孩子交换增加的密钥。

在斐波那契堆的情况下，在这个参考文献中，他们说斐波那契堆也支持增加键操作。但是，我在关于 Fibonacci Heaps 的原始论文中找不到任何关于它的内容，在 CLRS（Cormen 的算法简介）中也找不到任何内容。

有人能告诉我如何有效地实现增加键操作，同时又不干扰数据结构对所有其他操作的摊销界限吗？

我正在实施斐波那契堆以改进我的 Dijkstra 的最短路径算法。我的 insert 方法工作正常，接下来我需要做的是 extract-min。我正在关注 CLRS。请注意本书中提到的一些属性还没有在我的实现中，因为到目前为止这些功能都不需要它们，但我稍后会添加它们。

这是它提供的堆栈跟踪：

主要错误在 consolidate 函数的内部 while 循环的条件语句中给出。我还在代码中注释了这一行。出了什么问题？我的主要测试方法是从 1 - 10 中插入 10 个随机数，然后提取最小值直到它为空。第一次调用 extract-min 时发生错误。

上面提到的代码是不正确的，它给出了一些更接近 fib_n 的值。

在第 6 行除以 sqrt(5) 后，此代码绝对完美。

我的疑问是：

1. 除以 sqrt(5) 有什么意义，为什么只有 sqrt(5) 而不是任何其他数字？
2. 我可以使用地板或天花板（或任何其他）解决同样的问题，而不用除以根（5）吗？

非常感谢任何帮助/指导/资源！

我的代码如下：

以下案例使用此算法失败：

10 10 我的输出：4，正确的输出：5

10 200 我的输出：5，正确的输出：2

1234 12345 我的输出：2，正确的输出：8

（可能还有更多）

我想知道问题出在哪里以及如何解决？有没有更好的方法使用相同的基本原理？

我正在尝试做一个斐波那契堆，但我不明白为什么我在 consolidate 方法中出现“indexofboundsException”错误，我就像geek_for_geeks一样实现它，虽然它是用 C 语言编写的，但我是用 java 做的，它应该可以工作:(。

正如我所说，我正在尝试执行以消除斐波那契堆的最小值，插入成功，显示也成功，但是合并后，数组中出现错误：

IndexodboundsException 对我说，到目前为止，我已经按照 geekforgeeks 页面所说的那样实现了它，但也许它在 java 中找到了不同的事情要做，在 C 中它说：

我的班级 Nodo 是：

公共类 Nodo {

和我的类 FH（斐波那契堆）：

包 Fibonacci_Heap；公共类 FH {

}

在此处输入图像描述

异常堆栈跟踪如下所示：

在实现更大规模的数据库系统时，是否有特定的原因首选 B+-树而不是斐波那契堆？从图像中的复杂性分析来看，斐波那契堆似乎更快。