数据结构（邓俊辉）学习笔记】优先级队列 01——需求与动机

1. 应用需求

从今天开始，进入到第十章优先级队列。你将会看到这是一类非常有趣的数据结构，顾名思义，在逻辑上它们首先是队列。然而与常规的队列不同，其中元素接受访问的次序未必是先进先出，而是按照所谓的优先级进行访问。

以下，就首先让我们来通过几个具体的应用实例，体会设计和实现这种数据结构的用意所在。

我们的第一个应用场景是夜间门诊。假设某家医院在夜间只安排了一位医生值班，那么他将按照什么样的次序为到来的病人提供服务呢？如果只是一般的感冒发烧、头疼脑热，那么自然是采用先来先服务的次序。
  ~  
然而真实的场景要复杂得多。比如，倘若某位病人是发生了骨折，那么相对于一般病人，他更应该优先地接受处置和治疗，即便他是刚刚才到，而即便就在这位骨折病人接受处置的过程中，如果又有一位心脏病突发的病人到来，那么相对而言，骨折就显得不那么重要了。
  ~  
是的，在这个场景下，每一位医生都会将包括骨折病人在内的所有病人放在一边，而去优先治疗这位刚刚到来的心脏病患者。可以看到在这一场景中，此前的先到先服务的原则已经不再继续使用。

实际上在我们的电脑中，这样的场景每时每刻都在发生。因为当今的绝大多数操作系统都支持多任务，而操作系统对多任务的调度采用的策略也与门诊医生类似。如果将电脑类比于医院，那么 CPU 就类似于门诊医生而同时参与调度的计算任务，则可类比于同时等候门诊的一批病人。
  ~  
在这里，每一个任务都拥有一个指标，有的数值更大，有的数值略小。这些指标都是动态变化的，而操作系统总是会挑选其中指标最大的那个任务，交由 CPU 进行处理。
  ~  
在这里，每个任务所拥有的指标，可以类比于每个病人的病情严重程度。这个指标的数值越大，或者说病情越严重，则会优先接受服务。因此我们也称之为优先级别，或者简称优先级 priority。

在算法方面，这类的需求更是举不胜举。比如，在哈夫曼编码树的构造算法中，我们就需要将整个森林组织为某种高效的数据结构，从而使得我们可以反复地从中取出权重最小的两棵子树，并将它们合并之后，重新加入到森林之中。

而在基于扫描线策略的诸多算法中，我们也需要将所有的事件点组织为某种高效的数据结构，从而使得我们可以反复地从中取出最邻近的事件，完成相应的处理，并将可能生成的新事件加入到这个数据结构当中。

2. 计算模式

通过以上所举的几个实例，可以归纳出此类问题的一种典型模式。

这里有两个主体：

1. 首先是一个服务端，比如此前的医生或者 CPU；
2. 而另外还有一批客户，比如等候门诊的一批病人，或者同时参与调度的一批计算任务。

前者也可能是某个算法，比如 Huffman 编码算法，以及扫描线算法。而后者则是算法所需处理的一批数据对象，比如一组待编码的字符，或者空间中的一组点。

在这里，数据集中的每一个数据对象都有一个表示其重要程度的指标，称作优先级。

而这里的算法则是严格的按照各数据项的优先级来确定究竟应该接下来访问谁。这样一种访问方式，与此前的寻秩访问、循位置访问、循关键码访问乃至循值访问都不相同。既然这里的访问次序完全取决于各数据项的优先级，所以我们也不妨称之为“循优先级访问”（call by priority）。当然，这样的一种数据访问方式必须兑现和落实为某一类具体的数据结构。

这类结构需要能够记录并维护所有数据项之间的相对优先级，并且按照这种优先级通过调度器将最高优先级的元素输送给所对应的服务端或者算法。因此我们也将这类数据结构称作优先级队列 priority queue。

那么具体的 priority queue 应该提供哪些数据操作的接口呢？具体的应该如何定义呢？

3.功能接口

以下，首先给出 priority queue 的接口规范。

没错，操作接口规范，还不是具体的算法。因为根据以上所归纳的典型计算模式，这里所需要的优先级队列首先可以看作为是一个抽象数据类型 ADT，至于它的具体实现方式以及适用的场合，我们将来随后详细介绍。

既然只是一个待实现的接口，在这里我们就为每个接口增加 Virtual 前缀修饰符，并将它们都设作0，从而使之成为所谓的纯虚函数。以便强制要求随后给出具体的实现。而单纯的就形势而言，这里的操作接口无非是三个：

1. 通过 getMax()，我们可以随时取出在当前优先级最高的词条；
2. 而在这个数据项接受完处置之后，我们则可以通过 del Max() 将它从整个数据集中删除掉，就像病人在接受完治疗之后可以随即离开医院一样，这也是整个数据集动态变化的一种可能。
3. 当然还包括对称的另一种可能：也就是有时候我们需要引入新的数据项，因此我们可以借助 insert () 接口，这就犹如一位新来的病人加入到门诊室的候诊序列中。

从某种意义上讲，优先级队列也是对我们此前所介绍过的栈和队列的推广，相应地，栈和队列也可以看作是 priority queue 的特例。在这两类数据结构中，各元素的优先级都是一成不变的，完全取决于他们在这个集合中的插入次序。具体来说，对于栈而言，越是晚到的元素优先级越高，因此也更早地出栈并接受处置。而队列则与之恰好相反，越是更早到达的元素，优先级越高，因此也更早地出队并接受处置。

那么具体的这样一组 ADT 操作接口又当如何具体地实现呢？不同的实现效率又是如何的呢？不同实现方法各自又适合于哪些应用场合呢？