《计算思维与算法入门》 —2.6.2 优先队列

2.6.2  优先队列

优先队列（Priority Queue）是一种不必遵守队列先进先出特性的有序线性表，其中的每一个元素都赋予一个优先级（Priority），加入元素时可任意加入，但有最高优先级者（Highest Priority Out First，HPOF）最先输出。

图2-44  急诊病人的安排

就是优先队列的应用

像一般医院中的急诊室，当然以最严重的病患（如得SARS的病人）优先诊治，跟进入医院挂号的顺序无关，如图  2-44所示。或者在计算机中CPU的作业调度中，优先级调度（Priority Scheduling，PS）就是一种按照进程优先级“调度算法”（Scheduling Algorithm）进行的调度，这种调度会用到优先队列，优先级高的用户比一般用户拥有较高的优先权利。

假设有4个进程：P1、P2、P3和P4，其在很短的时间内先后到达等待队列，每个进程所需的运行时间如表2-3所示。

表2-3  每个进程所需的运行时间

在此设置进程P1、P2、P3、P4的优先次序值分别为2、8、6、4（此处假设数值越小其优先级越低，数值越大其优先级越高）。按优先级调度进程绘出的甘特图如图2-45所示。

图2-45  优先级调度进程的示意图

在此特别提醒大家，当各个元素以输入的先后次序为优先级时，就是一般的队列，假如以输入先后次序的倒序作为优先级，此优先队列其实就是一个堆栈。