二叉堆和斐波那契堆的实际应用领域

Question

斐波那契堆和二叉堆有哪些实际的应用？如果你能分享一些你使用它们解决问题的实例就太好了。

编辑：新增了二叉堆。很好奇。

- softwarematter

---

“真实世界的应用”似乎在问错问题，类似于“数组的真实世界用途是什么？” - Roger Pate

每个人都知道数组在现实世界中的用途！ - softwarematter

相关：有人真正高效地实现了斐波那契堆吗？。执行摘要：在大多数实际应用中，二叉堆优于斐波那契堆，除非底层图形非常密集。这基本上是因为二叉堆可以使用数组高效地实现，而斐波那契堆是作为指针系统实现的。 - ire_and_curses

@devnull：按照今天的网站标准，这个问题太过宽泛。我已经重新关闭了它以反映这一点。 - Martijn Pieters

斐波那契堆是一种极其特定的堆，它被发明出来证明一个限制。在基于指针的堆中，你通常会使用“实用”的数据结构——配对堆，这在你需要做大量堆合并的工作负载中尤为有用。如果您不需要合并或降低键值，则通常只需要使用标准库中的任何堆，它通常是在数组上实现的二叉或4叉堆。 - saolof

Answer 1

在实际生活中，你很少使用它。我认为 Fibonacci 堆的目的是改善 Dijkstra 算法的渐近运行时间。对于非常大的输入可能会给你提高，但大多数情况下，一个简单的二叉堆就足够了。

来自维基百科：

尽管以空结构开始的一系列操作的总运行时间受到上述界限的限制，但该序列中的某些（非常少数）操作可能需要很长时间才能完成（特别是删除和删除最小值在最坏情况下具有线性运行时间）。因此，Fibonacci 堆和其他分摊数据结构可能不适用于实时系统。

二叉堆是一种数据结构，可用于快速查找一组值中的最大（或最小）值。它在 Dijkstra 算法（最短路径）、Prim 算法（最小生成树）和 Huffman 编码（数据压缩）中使用。

- Peter Alexander

---

注意：斐波那契算法改善了平摊时间，而非最坏情况。同时，二叉堆的平均时间复杂度也是 O(1)。 - Ciro Santilli OurBigBook.com

Answer 2

不能确定斐波那契堆的情况，但二叉堆被用于优先队列中。优先队列在实际系统中得到广泛应用。

一个已知的例子是内核中的进程调度。最高优先级的进程首先被执行。

我曾在集合分区中使用过优先队列。将具有最大成员的集合首先用于分区。

- Manoj R

Answer 3

在大多数情况下，您需要根据以下复杂性进行选择：

• 插入
• 查找元素

通常的选择包括：

• BST：插入和查找都是log(n)
• 链表：插入为O(1)，查找为O(n)
• 堆：
  • 二叉堆平均插入为O(1)（请参见：https://dev59.com/MG025IYBdhLWcg3wNTEV#29548834）
  • 斐波那契堆平摊插入为强于平均但弱于最坏情况。
• 堆的查找仅适用于第一个元素，为O(1)，一般情况下为O(n)。
  • 对于二叉堆来说是最坏情况
  • 对于斐波那契堆来说是平摊的

还有{{link1：Brodal队列}}和其他堆可以达到最坏情况下O（1），但需要比Fibonacci更大的队列才能值得使用。

因此，如果您的算法只需要“查找”第一个元素并进行大量插入，则堆是一个不错的选择。

正如其他人提到的那样，这适用于Dijkstra算法。

- Ciro Santilli OurBigBook.com

Answer 4

优先队列通常被实现为堆，例如：http://download.oracle.com/javase/6/docs/api/java/util/PriorityQueue.html

使用二叉堆可以高效地计算出巨大数据集中的前N个元素（例如，在大型网站中搜索查询排名前N的结果）。

- Sheldon L. Cooper