21

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

  1. 斐波那契堆有很好的实现，包括标准库，如 Boost C++。这些库包含斐波那契堆的事实表明它们必须在某处有用。
  2. 我们知道斐波那契堆在实践中更快需要满足某些条件：“要在实践中从斐波那契堆中受益，您必须在减少键非常频繁的应用程序中使用它们”；"要使 Fibonacci Heap 真正发挥作用，您需要以下两种情况之一：a) 昂贵的比较：Fib Heaps 最大限度地减少了组织数据所需的比较次数。b) 大多数操作是 updateKey/insert/delete。作为 Fibonacci将更新‘分组’在一起，直到下一个 extractMin，‘batch’越大，它的效率就越高。 ”
  3. 有一种称为“Brodal Queue”的数据结构，我不确定我之前是否听说过它似乎具有至少与斐波那契堆一样好的时间复杂度行为。 这是一个很好的表格，其中比较了不同种类堆的各种操作的时间复杂度。
  4. 关于是否有任何应用斐波那契或二项式堆的问题，回答者仅给出了二项式堆的示例。
4

1 回答 1

30

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

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

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

希望这可以帮助！

于 2015-07-03T00:34:39.817 回答