数据结构（邓俊辉）学习笔记】优先级队列 02——基本实现_邓俊辉 数据结构 试题 答案

1. 向量

以下我们就来看看如何基于此前已掌握的基本数据结构来实现优先级队列。在这里我们既要考虑到效率，也要兼顾成本，而最佳的实现方式应该是这两个因素的综合与兼顾。

我们的第一种实现方式是基于此前的向量。也就是说将所有元素在底层组织为一个向量，这种实现方式非常简明，而且在某些方面效率还很高。比如对于每一个新加入的元素，我们只需简明地将它放到这个向量的末尾。

也就是说通过向量的 insertAsLast 接口就可以实现 PQ 的 insert 接口。我们知道，在向量中插入一个元素所需的成本应该与这个元素的秩成反比。
  ~  
|Vector :: insert(r,e) | = O(n - r)
  ~  
因此最后一个元素作为秩最高者，所需要的成本也会最低，具体来说也就是常数。

然而遗憾的是，为此我们却不得不在另外两个接口付出代价。为了找到优先级最高的元素，我们将不得不遍历整个向量。

也就是说，这一接口getMax() 的实现成本将是 $\theta$( n)。而为了摘除优先级最高的元素，我不仅需要遍历整个向量，而且需要在摘除之后将它的所有后继顺次前移。两项工作的成本累计也是$\theta$( n)。

因此无论如何，这都不是一个可行的解决方案。

2. 有序向量

你应该记得此前曾举过的多个实例，是的，如果始终将向量中的元素按顺序排列，也就是构成所谓的“有序向量”，往往可以使得算法的效率有实质的提高。那么这一策略在这里是否依然可行呢？我们不妨来尝试一下。

比如将整个向量组织成一个非降的有序序列。我很高兴地发现，此时最大的元素位置是确定的，它必然位于整个向量的末尾。因此无论是找到它，或是摘除它，都可以高效率地完成。具体来说，为此我们均只需 O（1）的常数时间。

然而依然很遗憾，这个有序序列的维护成本过高。为了插入一个新的元素，我们不仅需要花费 log n 的时间进行二分查找，而且更重要的是，我们需要提前将它的所有后继顺次后移，在最快的情况下，以及平均情况下，都需要花费线性的时间。

因此将向量有序化也不是一个行之有效的策略。

同样，借助列表也不能高效地实现优先级队列。

基于时间关系，我们这里只给出示意性的原理图，以及关于3个接口效率的结论，请你自行验证。

而与向量类似的一个坏消息是，即便我们采用有序化的策略，也无法兼顾优先级队列三个接口的高效性。也不妨对照我们这里所给出的原理图，就这三个接口的效率做一验证。

3. BBST

至此，你可能会想到求助于刚刚介绍过的强大的 BBST。

是的，无论是用 AVL 树、伸展树或者红黑树来实现优先级队列，三个标准接口的效率都可以保证达到大 O意义下的 log（n）。而且只需稍作优化，其中 getMax() 接口效率还可以进一步提高到 O(1)。然而，尽管如此，仅就优先级队列所要求的功能来说，BBST 的功能却过于强大了。难道不是这样吗？

将优先级队列与 BBST 的接口功能做一对比就会发现：

1. 相对于 BBST， 优先级队列的插入功能是完全一样的；
2. 然而 BBST 的 search（） 接口 在优先级队列中却只限定于针对最大元素。相对而言，充其量只能算半个查找。
3. 而 BBST 的 remove（）呢？在这里同样只限定于优先级最高的元素，因此同样的充值量不过是半个删除操作。

从这一角度来看，优先级队列充起量只不过是2/3个 BBST。也就是说我们实际上是使用了一种非常高级的数据结构来实现一种功能更为简单的结构，形象地说，也就是杀鸡用了牛刀。

那么，有没有成本更为低一点的实现方式呢？我们注意到，对于优先级队列来说，矛盾的焦点都集中在优先级最高的那个极值元素。是的，极值元素。这就意味着，我们实际上只需维护所有元素之间的一个偏序关系，就足以确定这个极值元素，而不必像 BBST 那样，始终都不折不扣地维护一个所有元素之间的全序关系。

根据这一分析，我们就有理由相信，的确可能存在某种形式上更为简单，而且维护成本更加低廉的实现方式。就接口的效率而言，我不妨参照 BBST 将实现的目标定做均为 log（n）。

那么这样一种实现方式具体如何？所设定的目标是否真的能够实现呢？