data-structures - Fibonacci 堆或 Brodal 队列是否在任何地方的实践中使用？

Question

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

There are good implementations of Fibonacci heaps out there, including in standard libraries such as Boost C++.这些库包含斐波那契堆的事实表明它们必须在某处有用。

我们知道斐波那契堆在实践中需要满足某些条件才能更快:“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. "

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是一个很好的表格，其中比较了不同种类堆的各种操作的时间复杂度。

在 a question about whether there are any applications of Fibonacci or binomial heaps ，回答者只给出了二项式堆的例子。

Answer 1

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

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

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

希望这可以帮助!