第6章 优先级队列

虽然通常都是将发送给打印机的作业放进队列里，但这并不是最好的做法。比如

• 作业A可能非常重要，期望的是只要有打印机可用，就立马运行作业A。
• 当打印机可用时，如果有若干个1页的作业，和一个100页的作业。比较合理的做法是让最长作业最后运行，即使该作业不是最后提交的。

在一个多用户环境中，操作系统调度器必须从多个进程中选择一个来运行。通常，一个进程只允许运行一段固定的时间。假如调度算法使用的是队列，实行的策略是作业最初是被放在队列的末尾；调度器会重复地取队列的第一个作业来运行，直到要么该作业完成了，要么时间耗尽了，该作业还没完成，就将它放到队列的末尾。这种策略通常是不合适的，因为由于要等待运行，非常短的作业似乎要花费很长时间。通常，短时作业应该尽可能快地完成，优先级要比正在运行的某些作业高。而且，有些作业虽不是短时作业，但也应该有优先级。
这类特殊的应用似乎需要一种特殊的队列：优先级队列。
在本章，我们将讨论：

• 抽象数据类型优先级队列的一种有效实现；
• 优先级队列的几种用法；
• 优先级队列几种高级实现；
• 本章中将看到的数据结构是计算科学中最优雅的数据结构之一；