这一部分我们介绍优先队列（Priority Queue）。
# 第 1 节 优先队列简介
# 「优先队列」与「堆」的关系
优先队列（Priority Queue）是一种「抽象的」数据结构；而堆（Heap）是具体的实现，这个系列我们只讲「二叉堆」，其它「优先队列」的实现不涉及。
# 优先队列用于解决什么样的问题
「优先队列」是从这样的场景中抽象出来的数据结构：班级里要选一名同学代表全班参加程序编程竞赛，此时我们只会关心第 1 名是谁。如果第 1 名不想参赛了，或者说第 1 名因为其它因素不符合参考资格，我们才考虑第 2 名，但也是从（除了第 1 名以外）剩下的那些同学中挑出第 1 名。
我们 只关心当前「最优」的那个元素，第 2 名、第 3 名直到最后一名都不考虑了。
「优先队列」相对于「普通队列」而言，「普通队列」的性质是「先进先出，后进后出」。「优先队列」由元素的 优先级 决定出队的顺序。
# 普通队列与优先队列
# 普通队列
「队列」是一种先进先出（FIFO）的数据结构，出队顺序谁先来谁先出去，有点先到先得的意思，日常生活中，随处可见的排队现象，抽象出来就是「队列」这种数据结构。
# 优先队列
同时在我们的生活中，有些情况下并不是按照谁先来，谁先处理的原则来处理事情。例如，我们自己的时间管理，我们会先处理最重要或者是最紧急的事情。又或者是在一些领域里，有些服务会针对 VIP 用户优先处理。「优先队列」的思想就类似与我们处理这一类问题，我们按照问题或者任务的重要程度（有的时候称之为优先级），处理更重要，优先级更高的事情，而不是来一个问题就马上处理解决这个问题。
| 普通队列 | 优先队列 |
|---|---|
| 先进先出，后进后出。元素入队的 时间顺序 决定了出队的顺序。 | 出队顺序与入队顺序无关，只与队列中元素的 优先级 有关，优先级最高的元素最先出队。元素的优先级决定了它会在什么时候出队。 |
# 更多「优先队列」在生活中的例子
「优先队列」更多地应用于动态的情况，即数据不是一开始就定好的，而是随时都有可能来新的数据，此时新数据与旧数据在一起选出「优先级」最高的那个元素。比如以下场景，重点理解「动态执行」这个概念：
- 医院看病：重症患者往往优先治疗，即使他（她）是后来者；
- 操作系统：选择优先级最高的任务执行；
- 上网：服务端依次回应客户端的请求：通常也是使用优先队列，优先级高的客户端优先响应；
下面是一个静态的例子：例：从
- 如果我们使用之前学习的排序算法，时间复杂度为：
，即先排序，再取出前 个元素。此时问题的时间复杂度完全由使用的排序算法决定； - 如果我们使用优先队列，那么解决该问题的时间复杂度为：
。与使用排序算法不同之处在于，我们只要维护有 个元素的数据结构就可以了，通常来说在这样的问题场景下 是远小于 的，例如上面说的「从 个数中选出最大的 个数， ， 」。
# 优先队列的主要操作
「优先队列」的主要操作有：
- 入队：把一个元素加入优先队列；
- 出队：把当前优先队列中优先级最高的元素拿出来；
- 查看优先队列中优先级最高的元素，也就是查看马上要出队的那个元素，只看它而不是取它。
作者：liweiwei1419 链接：https://suanfa8.com/priority-queue 来源：算法吧 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。