algorithm - 二进制堆和斐波那契堆的实际应用

Question

斐波那契堆和二叉堆的实际应用是什么？如果您可以在使用它来解决问题时分享一些实例，那就太好了。

编辑：还添加了二进制堆。很想知道。

Answer 1

你很少会在现实生活中使用一个。我相信斐波那契堆的目的是改善 Dijkstra 算法的渐近运行时间。对于非常非常大的输入，它可能会给您带来改进，但大多数时候，您只需要一个简单的二进制堆。

来自维基：

尽管以空结构开始的一系列操作的总运行时间受上述界限的限制，但序列中的一些（很少）操作可能需要很长时间才能完成（特别是 delete 和 delete minimum 在最坏的情况）。由于这个原因，斐波那契堆和其他摊销数据结构可能不适合实时系统。

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

Answer 2

不能说斐波那契堆，但优先级队列中使用了二进制堆。优先级队列在实际系统中被广泛使用。

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

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

Answer 3

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

• 插入
• 寻找元素

通常的嫌疑人是：

• BST：log(n)插入并查找
• 链表：O(1)插入和O(n)查找
• 堆：
  • O(1)插入
    • 二进制堆的平均值，请参阅：https ://stackoverflow.com/a/29548834/895245 ）
    • 为斐波那契摊销。这比平均水平要强，比最坏的情况要弱。
  • O(1)通常 只查找第一个元素O(n)
    • 二叉堆的最坏情况
    • 为斐波那契摊销

还有Brodal 队列和其他达到O(1)最坏情况的堆，但需要比斐波那契更大的队列才值得。

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

正如其他人所提到的，Dijkstra 就是这种情况。

Answer 4

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

从庞大的数据集中计算前 N 个元素可以使用二进制堆有效地完成（例如，大型网站中的热门搜索查询）。