Fibonacci堆或Brodal队列在实践中使用吗？

 

斐波那契堆是否在实践中用于任何地方？ 我环顾四周，找到了相关问题的答案（见下文），但实际上没有什么能够回答这个问题。

  • 斐波那契堆有很好的实现，包括标准库，如Boost C ++。 这些库包含斐波那契堆的事实表明它们必须在某处有用。
  • 我们知道斐波纳契堆在实践中需要满足某些条件：“在实践中受益于斐波那契堆，您必须在reduce_keys非常频繁的应用程序中使用它们;” “对于Fibonacci Heap来说，你需要满足以下任何一种情况：a）昂贵的比较：Fib堆最小化了组织数据所需的比较次数b）大部分操作是updateKey / insert / delete作为Fibonacci堆'组'更新在一起，直到下一个提取最小，'批'越大，效率就越高。“
  • 有一种称为“Brodal Queue”的数据结构，我不确定我是否听说过这种数据结构，但似乎时间复杂性的行为至少与斐波那契堆一样好。 这里有一张不错的表格，比较了不同种类堆的各种操作的时间复杂性。
  • 关于是否有任何斐波纳契或二项堆的应用问题，答复者只给出了二项堆的例子。

    • 就我所知，没有实际使用斐波那契堆或Brodal队列的主要应用程序。

    斐波那契堆最初被设计为满足理论而非实际的需要：渐近地加速Dijkstra的最短路径算法。 Brodal队列（以及相关的功能数据结构）的设计类似于满足理论保证，具体来说，是为了回答关于是否有可能将Fibonacci堆的时间范围与最坏情况保证相比较而不是摊销保证的长期悬而未决的问题。 从这个意义上说，数据结构并不是为满足实际需要而开发的，而是为了推进我们对算法效率极限的理论理解。 据我所知，目前没有算法在Fibonacci堆上使用Brodal队列实际上会更好。

    正如其他答案所指出的那样，隐藏在斐波那契堆或Brodal队列中的常数因子非常高。 他们需要在很多复杂的链表中连接很多指针，因此具有绝对可怕的引用位置，尤其是与标准二进制堆相比。 这意味着，除非您有需要大量减少键操作的算法，否则它们在实践中可能会在执行缓存效果时表现更差。 有些情况下会出现这种情况（例如，链接的答案会谈到其中的一些答案），但将它们视为高度专业化的情况而不是常见用例。 如果您正在处理巨大的图表，则更常见的是使用其他技术来提高效率，例如对近期问题使用近似算法，更好的启发式算法或使用底层数据的特定属性的算法。

    希望这可以帮助！

    链接地址: http://www.djcxy.com/p/39849.html

    上一篇: Are Fibonacci heaps or Brodal queues used in practice anywhere?

    下一篇: What data structures and algorithms are not implementable in C?