斐波纳契堆积或Brodal队列在实践中使用吗？ [英] Are Fibonacci heaps or Brodal queues used in practice anywhere?

问题描述

斐波纳契堆是否在实践中使用？我已经看了一下SO，找到了相关问题的答案（见下文），但没有什么可以真正回答这个问题。

1. 有很好的Fibonacci实现，包括标准库，如Boost C ++ 这些图书馆包含斐波那契堆的事实表明，它们在某处必须是有用的。


2. 我们知道，斐波纳契堆需要满足某些条件才能更快在实践中：在实践中受益于斐波那契堆，您必须在减少密钥难以置信的应用程序中使用它们 ; 对于斐波纳契堆真正闪耀，您需要以下任一情况：a）昂贵的比较： Fib堆最小化组织数据所需的比较数量b）大多数操作是updateKey / insert / delete。由于Fibonacci堆组更新一起直到下一个extractMin，批次越大，效率越高它得到。


3. 有一个名为Brodal Queue的数据结构，我不知道我以前听说过，似乎有时间复杂性行为至少与斐波纳契堆积一样。 这里是一个不错的表，与不同品种的各种操作的时间复杂性相比较的


4. 在关于是否有任何应用斐波纳契或二项式堆的问题，回答者只提供二项式堆的例子。

据我所知，没有实际使用斐波那契堆或布罗代尔队列的主要应用程序。

斐波纳契堆最初设计是为了满足理论而不是实际需要：渐近地加快Dijkstra的最短路径算法。 Brodal队列（以及相关的功能数据结构）的设计类似于满足理论保证，特别是回答一个长期存在的开放性问题，即是否可以将斐波纳契堆的时间范围与最坏情况的担保相匹配而不是摊余担保。在这个意义上，数据结构并不是为了满足实际需要而开发的，而是推动我们对算法效率极限的理论认识。据我所知，在Fibonacci堆中使用Brodal队列并不存在现有的算法。

正如其他答案所指出的那样，斐波纳契堆或Brodal队列中隐藏的常数是非常高的。他们需要很多指向许多复杂链接的指针，因此，具有绝对可怕的参考位置，特别是与标准二进制堆相比。这意味着，除非您有需要大量减少关键操作的算法，否则在实践中可能会更糟糕。有些情况出现（例如，链接的答案谈论了其中的几个），但将其视为高度专业化的情况，而不是常见的用例。如果您正在研究巨大的图形，使用其他技术来提高效率是比较常见的，例如使用近似算法来处理手头的问题，更好的启发式算法或使用基础数据的特定属性的算法。

希望这有帮助！

Are Fibonacci heaps used in practice anywhere? I've looked around on SO and found answers to related questions (see below) but nothing that actually quite answers the question.

1. There are good implementations of Fibonacci heaps out there, including in standard libraries such as Boost C++. The fact that these libraries contain Fibonacci heaps suggests to be that they must be useful somewhere.
2. We know that certain conditions need to be met for a Fibonacci heap to be faster in practice: "to benefit from Fibonacci heaps in practice, you have to use them in an application where decrease_keys are incredibly frequent"; "For the Fibonacci Heap to really shine, you need either of the following cases: a) Expensive comparisons: Fib Heaps minimize the number of comparisons required to organize the data. b) The majority of operations is updateKey/insert/delete. As Fibonacci Heaps 'group' the updates together until the next extractMin, the larger the 'batch', the more efficient it gets."
3. There is a data structure called a "Brodal Queue" which I'm not sure I'd heard of before that seems to have time complexity behaviors at least as good as Fibonacci heaps. Here's a nice table with a comparison of time complexities for various operations for different varieties of heaps.
4. On a question about whether there are any applications of Fibonacci or binomial heaps, answerers only gave examples of binomial heaps.

解决方案

To the best of my knowledge, there are no major applications that actually use Fibonacci heaps or Brodal queues.

Fibonacci heaps were initially designed to satisfy a theoretical rather than a practical need: to speed up Dijkstra's shortest paths algorithm asymptotically. The Brodal queue (and the related functional data structure) were similarly designed to meet theoretical guarantees, specifically, to answer a longstanding open question about whether it was possible to match the time bounds of a Fibonacci heap with worst-case guarantees rather than amortized guarantees. In that sense, the data structures were not developed to meet practical needs, but rather to push forward our theoretical understanding of the limits of algorithmic efficiency. To the best of my knowledge, there are no present algorithms in which it would actually be better to use a Brodal queue over a Fibonacci heap.

As other answers have noted, the constant factors hidden in a Fibonacci heap or Brodal queue are very high. They need a lot of pointers wired in lots of complicated linked lists and, accordingly, have absolutely terrible locality of reference, especially compared to a standard binary heap. This means that they're likely to perform worse in practice given caching effects unless you have algorithms that need a colossally large number of decrease-key operations. There are some cases where this comes up (the linked answers talk about a few of them, for example), but treat them as highly specialized circumstances rather than common use cases. If you're working on huge graphs, it's more common to use other techniques to improve efficiency, such as using approximation algorithms for the problem at hand, better heuristics, or algorithms that use specific properties of the underlying data.

Hope this helps!

这篇关于斐波纳契堆积或Brodal队列在实践中使用吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！