斐波那契堆或布罗达尔队列在实践中有被使用吗？

Question

"Fibonacci堆在实践中有用吗？我在SO上查找了相关问题的答案（见下文），但没有真正回答这个问题。"

1. 有一些很好的Fibonacci堆实现，包括在标准库中，比如Boost C ++。 这些库包含Fibonacci堆表明它们必须在某个地方有用。
2. 我们知道，在实践中，Fibonacci堆需要满足某些条件才能更快： "要想在实践中受益于Fibonacci堆，您必须将它们用于频繁进行降低键值的应用程序"; "对于Fibonacci堆真正闪耀的地方，您需要满足以下任一情况：a）昂贵的比较：Fib堆最小化组织数据所需的比较数量。 b）大多数操作是updateKey / insert / delete。由于Fibonacci堆将更新“分组”到下一个extractMin，因此批量越大，效率越高。"
3. 有一种名为“Brodal Queue”的数据结构，我不确定以前是否听说过，它似乎具有至少与Fibonacci堆相同的时间复杂度行为。 这里有一个漂亮的表格，列出了不同类型堆的各种操作的时间复杂度比较。
4. 在关于是否有任何Fibonacci或二项式堆的应用程序的问题，回答者只给出了二项式堆的例子。

- kuzzooroo

Answer 1

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

斐波那契堆最初是为了满足理论而非实际需求而设计的：以渐进方式加速Dijkstra最短路径算法。布罗代尔队列（及相关的函数数据结构）同样是为了满足理论保证而设计的，特别是为了回答一个长期存在的开放性问题：是否可能匹配斐波那契堆的时间界限，而不是摊销保证。从这个意义上说，数据结构并不是为了满足实际需求而开发的，而是为了推动我们对算法效率极限的理论理解。据我所知，目前没有任何算法会比使用斐波那契堆更好地使用布罗代尔队列。

正如其他答案所指出的那样，斐波那契堆或布罗代尔队列中隐藏的常数因子非常高。它们需要大量的指针连接在许多复杂的链表中，因此引用局部性绝对非常糟糕，特别是与标准二叉堆相比。这意味着，除非你有需要大量减小键操作的算法，否则它们在实践中可能表现更差。存在一些这种情况（例如，链接的答案谈论了其中一些），但是将它们视为高度专业化的情况而不是常见用例。如果您正在处理大型图表，则更常见的是使用其他技术来提高效率，例如针对所涉及问题的近似算法，更好的启发式或使用底层数据的特定属性的算法。

希望这可以帮到你！

- templatetypedef

---

关于近似算法的观点非常有道理。当问题变得足够大，可以从这些高级数据结构中受益时，您可能愿意接受近似值，此时计算速度会更快。 - kuzzooroo

Answer 2

斐波那契堆在生物信息学短读序列组装工具Velvet中使用。

请参见论文“复杂性和扩展问题”部分：https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2336801/

摘录，重点是我自己加的：

就时间和内存而言，主要瓶颈在于图形构建。Streptococcus reads的初始图需要2.0 Gb的RAM。随着问题规模的扩大，整个基因组组装需要持久内存数据结构。可以承认，访问时间会更长，但可存储的数据量将几乎无限制。Tour Bus的时间复杂度主要取决于图形中节点数N，它本身取决于读取覆盖范围、误差率和重复次数。Idury和Waterman（1995）估计了N但忽略了重复。搜索本身基于Dijkstra算法，当使用Fibonacci堆实现时，其时间复杂度为O（N logN）（Gross and Yellen 2004）。单个路径比较的成本以及相应的图形修改可以通过长度截止值进行限制。

- fwip

---

是的，在 https://github.com/dzerbino/velvet/blob/master/src/fib.h 的源代码中找到了。 - kuzzooroo