浅谈优先队列

左手的ㄟ右手 2022-05-26 09:56 66阅读 0赞

# 浅谈优先队列 #

## 一道面试题 ##

如果你被问到：  
“编写一个程序，从 10 亿个元素的整数数组中找出前10个最大的数。”  
你会怎么回答？

我想，最最简单的回答就是蛮力法：先对这10亿个数排序（比如用时间复杂度为 O(nlogn)  O ( n log ⁡ n )  的快速排序），然后选出前10个最大的。

请问有更好的方法吗？

## 优先队列是什么 ##

普通的队列是一种先进先出的数据结构：从队尾追加元素，从队首删除元素。

在优先队列中，元素被赋予优先级。出队时，具有最高优先级的元素被删除，也就是说，优先队列具有最高优先级先出（largest-in，first-out）的行为特征。

优先队列支持两种**基本操作**：

1.  向优先队列插入一个新元素
2.  删除（或得到）优先队列中优先级最高的元素

对于本文开始的问题，如果你知道了有“优先队列”这么一说，则很容易想到下面的解决办法：

1.  建立大小为 10 的容器
2.  从数组中读取一个数到变量`temp`
3.  如果容器没有满，则把`temp`加入容器；如果容器已满，则找出容器中最小的数（利用优先队列的性质）和`temp`比较：若`temp`较大，则最小元素出队，`temp`入队；若`temp`较小，转到 4
4.  重复2~3，直至读完整个数组，此时容器中的 10 个数就是所求。

此外，上述方案可以并行方式运行，最后合并结果。

除了上面的例子，优先队列还有一些重要的应用场景。

比如作业（或者说任务）调度，当一个作业完成后，需要在所有等待调度的作业中选择一个优先级最高的作业来执行，并且也可以添加一个或多个新的作业到优先队列中。

再比如排序，通过插入一系列元素，然后一个个地删除其中最小的元素，就可以实现从小到大的排序。一种名为“堆排序”的重要排序算法正是利用了基于“堆”实现的优先队列。

## 优先队列的实现 ##

### 用无序数组实现 ###

对于入队操作，直接把元素追加到数组尾部。时间复杂度为 O(1)。

对于出队操作，需要遍历数组，找出优先级最高的元素，并删除之，空缺的位置由后面的元素依次补上。因此，出队的时间复杂度为 O(n)。

### 用有序数组实现 ###

对于入队操作，由于要求数组有序，所以在插入元素的时候需要遍历数组以找到适合的位置，然后在该位置插入，同时此位置后面的元素要依次向后移动，时间复杂度为 O(n)。

对于出队，由于序列是有序的，所以时间复杂度为 O(1)。

### 用链表实现 ###

用链表实现和数组类似，也可分为无序和有序两种，不同的是采用链式存储结构，省去了移动元素的麻烦。

### 用堆实现 ###

上面三种实现思路其实都不怎么好，不是入队的时间复杂度为 O(n)，就是出队的时间复杂度为 O(n). 有没有更好的实现呢？有一种数据结构叫“堆”，基于堆实现的优先队列，出队和入队的时间复杂度都为 O(logN).

堆到底是什么，都有哪些性质，具体怎么实现……这一系列的问题，咱们下回聊。

【未完待续】

**参考资料**  
[https://allenwind.github.io/2017/09/12/%E4%BC%98%E5%85%88%E9%98%9F%E5%88%97%E7%9A%84%E4%BA%94%E7%A7%8D%E5%AE%9E%E7%8E%B0/][https_allenwind.github.io_2017_09_12_E4_BC_98_E5_85_88_E9_98_9F_E5_88_97_E7_9A_84_E4_BA_94_E7_A7_8D_E5_AE_9E_E7_8E_B0]

[https_allenwind.github.io_2017_09_12_E4_BC_98_E5_85_88_E9_98_9F_E5_88_97_E7_9A_84_E4_BA_94_E7_A7_8D_E5_AE_9E_E7_8E_B0]: https://allenwind.github.io/2017/09/12/%E4%BC%98%E5%85%88%E9%98%9F%E5%88%97%E7%9A%84%E4%BA%94%E7%A7%8D%E5%AE%9E%E7%8E%B0/