算法导论第6.5章 - 优先队列

优先队列
优先队列是堆的一个应用。
优先队列是一种用来维护由一组元素构成的集合S的数据结构，每个元素有一个key。

最大优先队列 （集合S）
支持操作

• 插入元素x之后，集合S等价于 S ∪ {x}
• 返回最大key的元素
• 去掉并返回S中的具有最大key的元素
• 提升某个元素的key

最大优先队列的应用
例如：共享计算机系统的作业调度。比较各个作业的优先级。当某个作业发生中断后，在其他待完成的作业中选出另一个最优作业。也可以随时可以插入新的作业，或者调整作业的优先级。

相应的有最小优先队列。