STL中的Fibonacci Heap在哪里？如果STL没有实现Fibonacci Heap在STL中使用现有算法和容器实现它的最佳实践是什么？
我最近使用两种数据结构初步比较了Dijkstra算法的运行时间,基于Java的PriorityQueue(基于二进制堆,如果我没有弄错的话)和Fibonacci堆.我使用Java的currentTimeMillis()来进行计算.我最终得到的结果非常有趣.这是我的一个测试用例的输出:
Running Dijkstra's with 8 nodes and 27 links
- Execution time with binary heap: 1 miliseconds
- Execution time with Fibonacci heap: 4 miliseconds
不可否认,我目前在数据集方面很缺乏,上面的图表是我最大的(我计划尽快制作).但这有什么意义吗？我一直认为Fibonacci堆比其他数据结构更快,因为与其他数据结构相比,它们的运行时间分摊了.我不确定这个3毫秒差异来自哪里.(我在Intel Core Ivy Bridge i7-3630M处理器上运行它,如果有帮助的话.)
注意:我偶然发现了这个可能解释这个问题的线程,尽管我仍然不清楚为什么Fibonacci堆版本需要更长的时间.根据该线程,可能是因为我的图形不够密集,因此reduce-Key操作的数量不足以使Fibonacci堆的性能真正发光.这是唯一合理的结论,还是我还缺少其他的东西？
我需要在我的项目中使用Fibonacci堆,我试图从boost库中使用它.但我无法弄清楚如何为任意数据类型设置用户定义的比较函数.我需要为struct node构造一个min heap,如下所示:
struct node
{
int id;
int weight;
struct node* next;
/* dist is a global array of integers */
bool operator > (struct node b) //Boost generates a Max-heap. What I need is a min-heap.
{return dist[id] < dist[b.id] ? 1:0 ;} //That's why "<" is used for "operator >".
bool operator < (struct node b)
{return dist[id] > dist[b.id] ? 1:0 ;}
bool operator >=(struct node b)
{return dist[id] <= dist[b.id] ? 1:0 ;}
bool operator …我正在使用boost::fibonacci_heapBoost 1.53.0 中的类来维护可更新的优先级队列。
当我想要更新一个元素时，我需要将堆中的元素与我想要替换它的新元素进行比较。我只想用“较小”版本替换堆中的元素，因此我想在更新之前对它们进行比较。
当我插入元素时，我存储它们的句柄（boost::fibonacci_heap::handle_type）。我在文档fibonacci_heap中看到的所有采用句柄类型的函数仅提供某种写访问权限（update()、decrease()等increase()），并且不允许我在更新句柄之前检查句柄标识的元素。
fibonacci_heap有没有什么方法可以仅使用句柄来查看 a 中的元素？
在教自己的Fibonacci Heap时我有这个问题,现在我知道这是一种有效的数据结构,可以O(1)在降低堆中元素的优先级时实现具有分摊时间复杂度的优先级队列.然而,根据CLRS教科书,优先级降低操作假定节点保持目标元素是预先知道的.我很好奇如果不是最小节点,我怎么能有效地获得所需的节点.一个简单的实现和分析会产生O(n)最坏情况下的时间复杂度,以便在Fibonacci堆上执行查找操作,与其他操作相比效率较低.所以我的问题是在Fibonacci Heap中有一个有效的查找操作,还是有必要的？
斐波那契堆在摊销意义上是有效的，但在最坏的情况下它们的效率如何？具体来说，在 n 节点斐波那契堆上，这些操作中的每一个的最坏情况时间复杂度是多少？
algorithm big-o time-complexity data-structures fibonacci-heap
我正在实现 Fast Marching 算法，它是某种连续 Dijkstra 算法。正如我在许多论文中读到的那样，斐波那契堆是最适合此目的的堆。
然而，当使用 callgrind 分析我的代码时，我发现以下函数占用了 58% 的执行时间：
int popMinIdx () {
const int idx = heap_.top()->getIndex();
heap_.pop();
return idx;
}
具体来说，它pop()占用了整个执行时间的 57.67%。
heap_定义如下：
boost::heap::fibonacci_heap<const FMCell *, boost::heap::compare<compare_cells>> heap_;
花费“那么多”时间是否正常，或者我可以做些什么来提高性能？
抱歉，如果没有提供足够的信息。我尝试尽可能简短。如果需要，我会添加更多信息。
谢谢你！
我想证明具有n个节点的Fibonacci堆可以具有高度n.
我用例子尝试了这个,但我不知道如何在一般情况下显示这个.