algorithm - 我什么时候使用优先队列？

Question

我所知道的使用优先级队列的唯一示例是 Dijkstra 算法（用于计算最小成本）

在其他什么情况下它会有用？

Answer 1

这是一个实际示例 - 对于业务应用程序：

你在经营一家医院，病人进来了。工作人员只有一名医生。第一个男人走进来——他马上就上菜了。接下来，一个感冒的人进来并需要帮助。您将他添加到队列中，他会排队等候医生有空。接着，一个头上插着斧头的人从门里走了进来。他被分配了更高的优先级，因为他有更高的医疗责任。所以感冒的人被排成一排。接下来，有人带着呼吸问题进来。所以，再一次，感冒的人被优先撞倒。这在现实世界中被称为分类——但在这种情况下，它是一条医疗线。

在代码中实现这一点将使用优先级队列和工作线程（医生）对消耗品/工作单元（患者）执行工作

Answer 2

基于堆的优先级队列对输入序列进行部分排序。当您不需要整个序列时，这比直接对其进行排序具有优势，因为 mcdowella 给出了一些示例。特别是，如果您只需要 n 个元素中的 m 个，则复杂度为 O(m log n)。第二个优势是当您动态添加元素时，即当您事先不知道整个序列时。使用堆作为后备存储，添加另一个元素比将其插入到排序序列中更快。

此外，当您按排序顺序弹出单个元素然后丢弃它们时（即，之后您不需要排序顺序），使用优先级队列可以为读者提供正确的消息。它还使得交换不同的实现变得相当容易，例如基于堆的实现或预先对输入序列进行排序的实现。虽然这是一个品味问题，您始终可以使用随后相应使用的任何序列来实现相同的目的，但这只会使代码更难阅读。

Answer 3

扫描大量统计数据以报告前 N 个项目 - N 个最繁忙的网络连接、N 个最有价值的客户、N 个最大的磁盘用户……

Answer 4

以下是列表： 事件驱动模拟： 客户排成一列，粒子碰撞

数值计算。 减少舍入误差 数据压缩。 压缩数据的霍夫曼代码。 图搜索：Dijkstra 算法、Prim 算法 数论： 幂和 人工智能： A* 搜索 统计： 保持序列中的最大 M 值 操作系统： 负载平衡、中断处理 离散优化。 装箱，调度 垃圾邮件过滤。 贝叶斯垃圾邮件过滤器

Answer 5

优先级队列（最小/最大堆）有很多应用。但是，如果您正在寻找经典和著名的算法Prim 的算法来为加权无向图找到最小生成树，例如，使用优先级队列。