问题标签 [fibonacci-heap]

我不认为 c++ 优先级队列是 dijkstra 队列的正确结构，因为它不包含用于轻松查找或删除元素的功能。

正确的结构是斐波那契堆，但 std 库中没有。

有人对更好的 C++ 实现结构有建议吗？

删除元素后，擦除操作是否也会更新堆？

我在 fibonacci_heap 的 boost 文档中浏览了成员函数解释，其中提到了增加/减少操作后会发生什么，但是当谈到擦除时，唯一说明的是它擦除了句柄指向的元素。

这是否意味着堆在那之后被改革了？如果没有，被擦除节点的子节点会发生什么？我错过了一些明显的东西吗？

我一直试图在这里理解斐波那契堆实现代码，并尝试使用似乎不起作用的简单测试用例进行测试。我插入了 3 个节点，然后每次都打印最小值，但答案是错误的。

预期的输出应该是

但上述代码的实际输出是

有人可以告诉我我在哪里做错了。是实现错误还是我没有正确理解代码？

编辑 - 1：添加了下面的整个代码：

我正在尝试实现Dijkstra 的算法，以使用Fibonacci Heap和图的邻接表表示来查找节点之间的最短路径。根据我知道的算法，我们必须在堆中找到最小节点，然后遍历它的所有邻居并更新它们的距离。但是要获得邻居的当前距离（存储在堆中的每个节点中），我必须从堆中找到那个特定的节点。“查找”操作需要 O(N) 时间，其中 N 是斐波那契堆中的节点数。那么我的算法是正确的还是我错过了什么？任何帮助将不胜感激。

我正在单独研究斐波那契堆，我遇到了一个问题。

我知道任何节点都可以插入斐波那契堆，但是如果该新节点的等级（或值或键）等于兄弟节点怎么办？

1）例如，

如果插入（1）的节点会发生什么？

2）或者在这种情况下会发生什么？

前：

后：

新的节点树属于哪里？

3）你将如何整合（或排序）这种树 - 在根部有一对相等的节点？

如果有人能帮我解决斐波那契堆上的这个小困惑，我将不胜感激。谢谢你。

我试图在我的实现中使用来自 boost 的斐波那契堆，但是我的程序崩溃了，当我调用 reduce 函数时，这个例子（W 是一个简单的类）：

斐波那契堆在任何地方都在实践中使用吗？我环顾四周，找到了相关问题的答案（见下文），但没有什么能真正回答这个问题。

1. 斐波那契堆有很好的实现，包括标准库，如 Boost C++。这些库包含斐波那契堆的事实表明它们必须在某处有用。
2. 我们知道斐波那契堆在实践中更快需要满足某些条件：“要在实践中从斐波那契堆中受益，您必须在减少键非常频繁的应用程序中使用它们”；"要使 Fibonacci Heap 真正发挥作用，您需要以下两种情况之一：a) 昂贵的比较：Fib Heaps 最大限度地减少了组织数据所需的比较次数。b) 大多数操作是 updateKey/insert/delete。作为 Fibonacci将更新‘分组’在一起，直到下一个 extractMin，‘batch’越大，它的效率就越高。 ”
3. 有一种称为“Brodal Queue”的数据结构，我不确定我之前是否听说过它似乎具有至少与斐波那契堆一样好的时间复杂度行为。 这是一个很好的表格，其中比较了不同种类堆的各种操作的时间复杂度。
4. 关于是否有任何应用斐波那契或二项式堆的问题，回答者仅给出了二项式堆的示例。

我正在使用 boost::fibonacci_heap 库实现一个快速行进算法，并且我开始使用它们的句柄来操作元素。

我已经编写了下面的基本代码，它编译得很好，但我不明白它的行为：

我首先将每个推送元素的句柄存储在一个数组中。然后我从堆中弹出第一个元素，并检查堆大小是否减小。

但后来我尝试使用它的句柄更新弹出的元素的值。此操作有效（令人惊讶？），更新的元素现在位于堆的顶部。但是堆大小保持不变，因为我没有正确地推入一个新元素。

那么当弹出的元素更新并返回堆时会发生什么？堆仍然有效吗？

终端输出：

斐波那契堆在摊销意义上是有效的，但在最坏的情况下它们的效率如何？具体来说，在 n 节点斐波那契堆上，每个操作的最坏情况时间复杂度是多少？

• 找到最小值
• 删除分钟
• 插入
• 减少键
• 合并