斐波那契堆或布罗达尔队列是否在实践中在任何地方使用? [英] Are Fibonacci heaps or Brodal queues used in practice anywhere?

问题描述

斐波那契堆在实践中是否在任何地方使用?我环顾四周，找到了相关问题的答案(见下文)，但实际上并没有完全回答这个问题.

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. 斐波那契堆有很好的实现，包括标准Boost C++ 等库.这些库包含斐波那契堆的事实表明它们必须在某处有用.
2. 我们知道需要满足某些条件才能使斐波那契堆在实践中更快:在实践中受益于斐波那契堆, 你必须在一个使 reduce_keys 非常频繁的应用程序中使用它们";"要使斐波那契堆真正发挥作用，您需要以下两种情况之一:a) 昂贵的比较:Fib Heaps 最小化组织数据所需的比较次数.b) 大多数操作是 updateKey/insert/delete.由于 Fibonacci Heaps 将更新分组"在一起直到下一个 extractMin，batch"越大，效率越高"
3. 有一种数据结构叫做我不确定我之前是否听说过Brodal Queue"，它的时间复杂度行为至少与斐波那契堆一样好. 这里是一个很好的表格，比较了不同堆的各种操作的时间复杂度.
4. 关于关于斐波那契是否有任何应用的问题或二项式堆，回答者只给出了二项式堆的例子.

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.

推荐答案

据我所知，没有真正使用斐波那契堆或 Brodal 队列的主要应用程序.

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

斐波那契堆最初的设计目的是满足理论需求而不是实际需求:渐近地加速 Dijkstra 的最短路径算法.Brodal 队列(以及相关的功能数据结构)的设计类似，旨在满足理论保证，特别是回答一个长期悬而未决的问题，即是否有可能将斐波那契堆的时间界限与最坏情况保证而不是摊销保证相匹配.从这个意义上说，数据结构不是为了满足实际需要而开发的，而是为了推进我们对算法效率极限的理论理解.据我所知，目前还没有在斐波那契堆上使用 Brodal 队列实际上更好的算法.

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.

正如其他答案所指出的，隐藏在斐波那契堆或 Brodal 队列中的常数因子非常高.它们需要连接在许多复杂链表中的大量指针，因此，具有绝对糟糕的引用局部性，尤其是与标准二进制堆相比.这意味着在给定缓存效果的情况下，它们在实践中的性能可能会更差，除非您的算法需要大量减少键操作.在某些情况下会出现这种情况(例如，链接的答案讨论了其中的一些)，但将它们视为高度专业化的情况而不是常见的用例.如果您正在处理大型图，则更常见的是使用其他技术来提高效率，例如使用近似算法解决手头的问题、更好的启发式方法或使用基础数据特定属性的算法.

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.

希望这有帮助！

这篇关于斐波那契堆或布罗达尔队列是否在实践中在任何地方使用?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！