索引优先队列-IndexedPrirotyQueue的原理及实现（源码）

1.索引优先队列的意义

索引优先队列是一个比较抽象的概念，它是一个优先队列，又带有索引，这个索引是用来干什么的呢？

在正常的队列中，我们只能访问队列头元素，整个队列中的元素我们都无法访问。那么对于这些队列中的元素，如果我们有一个映射，能够知道队列中的第m个元素到底对应我们把所有元素加入优先队列之前的哪一个，那要使用它岂不是方便许多？

我们知道，在优先队列中，一个元素加入队列之后的顺序不是固定的，有可能上浮或者下沉。那么，我们怎么知道我们加入队列的这个元素，到底在队列中的什么位置呢？

这就是索引优先队列的用途。它用一个索引数组保存了某个元素在优先队列中的位置。

例如：

prirotyQueue[i] = j; //索引优先队列的第i个元素的值是j
Index[j] = i; //那么，我们需要的这个元素j在优先队列中的位置就是i

这样，当我们需要用这个元素j的时候，我们就能直接找到j的位置是优先队列的第i个。

2.索引优先队列的实际应用

（1）从上面的内容看，好像我们知道这个索引也没什么实际用处，真的是这样吗？

考虑下面一种情况，比如李雷考了全班第一，韩梅梅考了第二。我们把全班四十个人的成绩按照高低排了优先队列。但是复核的时候，突然发现韩梅梅的成绩少算了10分，加上10分应该她是第一。那么，如果没有这个索引，我们要怎么修改已经形成的优先队列呢？

有的人可能说，很简单啊，把李雷和韩梅梅出队列，然后更改成绩，重新加入队列。

好，那么，假如韩梅梅成绩统计错了，她是全班第三十九人呢？难道要把39个人的成绩重新出队列，然后重新加入吗？这个成本代价似乎有点高。

更进一步，如果是全校四千人的队列呢？如果有一千人的成绩全算错了呢？我们要重新生成这个队列一千次？

这时候，索引优先队列就有了用武之地。如果韩梅梅的成绩错了，我们从索引里知道她是优先队列里的第二个，那么我们直接修改她的成绩，然后上浮或者下沉就可以了，要付出的代价非常小。

（2）再进一步，如果要按成绩排队之后，依次请家长上台传授家教经验呢？我们怎么知道每个人的家长是谁啊？

这时候，我们再用一个数组key[]，其中保存了每个人和家长的名字对应关系。这样来看，有一个索引的用处是不是更大了？

把这些合起来，就得到第三部分的索引优先队列IndexedPQ的实现。

3.索引优先队列的API和实现

在很多应用中，允许用例引用已经进入有限队列中的元素是有必要的。做到这一点的一种简单方法是用例已经有了总量为N的多个元素，而且可能还同时使用了多个（平行）数组（Parallel Array）来存储这些元素的信息。此时，其他无关的用例代码可能已经在使用一个整数索引来引用这些元素了。这些考虑引导我们设计了下表。

理解这种数据结构的一个较好方法是将它看成一个能够快速访问其中最小元素的数组。事实上它还要更好——它能够快速访问数组的一个特定子集中的最小元素（指所有被插入的元素）。换句话说，可以将名为pq的IndexMinPQ优先队列看做数组pq[0..N - 1]中的一部分元素的代表。将pq.insert(k, item)看做将k加入这个子集并使pq[k] = item, pq.change(k, item)则代表令pq[k] = item。这两种操作没有改变其他操作所依赖的数据结构，其中最重要的就是delMin()（删除最小元素并返回它的索引）和change()（改变数据结构中的某个元素的索引——即pq[i] = item）。这些操作在许多应用中都很重要并且依赖于对元素的引用（索引）。一般来说，当堆发生变化时，我们会用下沉（元素减小时）或上浮（元素变大时）操作来恢复堆的有序性。在这些操作中，我们可以用索引查找元素。能够定位堆中的任意元素也使我们能够在API中加入一个delete()操作。

命题Q（续）。在一个大小为N的索引优先队列中，插入元素（insert）、改变优先级（change）、删除（delete）和删除最大小元素（remove the minimum）操作所需的比较次数和logN成正比（如后表）

证明。已知堆中所有路径最长即为~lgN，从代码中很容易得到这个结论。

以下是《alg4》书中实现的一个找出最大元素的索引优先队列的JAVA版本IndexMaxPQ.java。