浅谈优先队列

一道面试题

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

我想，最最简单的回答就是蛮力法：先对这10亿个数排序（比如用时间复杂度为 $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/

最后

以上就是激动柚子为你收集整理的浅谈优先队列浅谈优先队列的全部内容，希望文章能够帮你解决浅谈优先队列浅谈优先队列所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。