数据机构与算法--索引优先队列
图片来自nullzx的博客园
索引优先队列，用一个索引数组保存了元素在数组中的位置。在插入队列中时，可看作将一个整数和一个对象相关联，使得我们可以引用队列中的元素。比如在Dijkstra算法中就用到了索引优先队列，他将顶点（整数表示）和源点到该顶点的最短路径长度关联起来，每次删除最小元素，都能得到与之关联的那个整数；如果该整数已经被关联了，还可以更新与该整数关联的对象。可以看出，索引优先队列和优先队列比起来，操作数组里面的元素更加方便了——这就是关联了索引带来的好处。
我们使用Key[] keys保存对象，int[] pq保存对象在数组中的位置，比如pq[1] = 5，那么keys[pq[1]] = keys[5]表示整数5和对象关联，而这个整数5存放于pq索引为1的位置；用一个int[] qp保存pq的逆序，即如果pq[i] = j（表示数组pq索引为i的位置存放了一个被关联的整数j），则有qp[j] = i，因此qp保存的是被关联整数j在数组pq中的索引。易知pq[qp[j]] = j; qp[pq[i]] = i
要注意的是，pq数组存放的关联整数是连续的，而qp和keys数组中存放的元素不是连续的，他们的位置是一一对应的。如果整数i还没有被关联，总是令qp[i] = -1，因此对应地keys[i] = null
自始至终keys数组中的元素位置不会发生变化，这就是说所有上浮下沉操作后，keys中元素的相对位置都不会变化，变化的只是与之关联的索引pq还有qp而已。（反正都能通过pq数组中存放的关联整数快速找到keys数组中的元素，所以只改变pq和qp中元素的相对位置足矣）
下图是将与整数3关联的对象替换成“a”.
这是一个小顶堆，pq是优先队列，但是它优先级的顺序并不是按照其关联的整数来排列的，而是按照关联整数对应的对象的大小来排列，即keys[pq[i]]。因此可以写出用于比较两个元素的less或者greater方法，我们先实现基于小顶堆的索引优先队列，它可以快速找到或者删除最大元素，所以greater方法如下
private boolean greater(int i, int j) {
return keys[pq[i]].compareTo(keys[pq[j]]) > 0;
}
可以删除最小元素的IndexMinPQ
我们的所有关键方法几乎都以greater方法为基础，理解它尤为重要。以下是完整实现。
package Chap9;
import java.util.Arrays;
import java.util.NoSuchElementException;
public class IndexMinPQ<Key extends Comparable<Key>> {
private int N;
private int[] pq; // 索引二叉堆，按照惯例从1开始
private int[] qp; // 逆序，满足qp[pq[i]] = pq[qp[i]] = i
private Key[] keys;
public IndexMinPQ(int maxN) {
// 可存放范围为[0, maxN]
keys = (Key[]) new Comparable[maxN + 1];
// 索引二叉堆,存放范围为[1, maxN]
pq = new int[maxN + 1];
// 可存放范围为[0, maxN]
qp = new int[maxN + 1];
// 刚开始没有关联任何整数，都设置为-1
Arrays.fill(qp, -1);
}
// 针对是pq中的索引i、j，但是实际引用的是keys中对应的元素
private boolean greater(int i, int j) {
return keys[pq[i]].compareTo(keys[pq[j]]) > 0;
}
public boolean isEmpty() {
return N == 0;
}
public int size() {
return N;
}
public boolean contains(int k) {
return qp[k] != -1;
}
public void insert(int k, Key key) {
if (!contains(k)) {
N++;
pq[N] = k;
qp[k] = N;
keys[k] = key;
swim(N);
}
}
// 给整数k重新关联一个对象
public void replace(int k, Key key) {
keys[k] = key;
// 由于和k关联的新key可能大于原来的key（此时需要下沉），也有可能小于原来的key（此时需要上浮），为了简化代码，既上浮又下沉，就囊括了这两种可能。
swim(qp[k]);
sink(qp[k]);
}
// 返回最小元素
public Key min() {
return keys[pq[1]];
}
// 最小元素的关联整数
public int minIndex() {
return pq[1];
}
public int delMin() {
if (isEmpty()) {
throw new NoSuchElementException("队列已经为空，不能执行删除！");
}
int indexOfMin = pq[1];
// 堆顶和最后一个元素交换
swap(1, N--);
sink(1);
// 最后一个元素置为空
keys[indexOfMin] = null;
// 同时关联整数pq[N]在pq中的的索引设置为-1，表示还没有对象与该整数关联
qp[indexOfMin] = -1;
return indexOfMin;
}
public void delete(int k) {
if (!contains(k)) {
throw new NoSuchElementException("没有元素与" + k + "关联！");
}
// index为整数k在pq中的位置
int index = qp[k];
swap(index, N--);
// 这里一定要先上浮下沉后再将元素置空，因为swim方法没有N的限制，在没有交换元素的情况下，即删除的就是pq中最后一个元素，如果先置空, 会在greater方法中引发空指针
// 而sink方法有N的限制，先置空后置空都没有影响，2k <= N会限制它进入循环，避免了空指针
swim(index);
sink(index);
keys[k] = null;
qp[k] = -1;
}
public Key keyOf(int k) {
if (contains(k)) {
return keys[k];
}
// 没有与k关联就返回null
return null;
}
private void swap(int i, int j) {
int temp = pq[i];
pq[i] = pq[j];
pq[j] = temp;
// 还要更新qp
qp[pq[i]] = i;
qp[pq[j]] = j;
}
private void swim(int k) {
// k = 1说明当前元素浮到了根结点，它没有父结点可以比较，也不能上浮了，所以k <= 1时候推出循环
while (k > 1 && greater(k / 2, k)) {
swap(k / 2, k);
// 上浮后，成为父结点，所以下标变成原父结点
k = k / 2;
}
}
private void sink(int k) {
// 父结点的位置k最大值为 N/2,若k有左子结点无右子结点，那么2k = N；若两个子结点都有，那么2k + 1 = N
// 有可能位置k只有左子结点，依然要比较，用2k + 1 <= N这个的条件不会执行比较，所以用2k <= N条件
while (2 * k <= N) {
int j = 2 * k;
// 可以取j = N -1,greater(N -1, N);由于下标从1开始，所以pq[N]是有元素的
if (j < N && greater(j, j + 1)) {
// 右子结点比左子结点大 ，取右子结点的下标
j++;
}
// 左子结点或者右子结点和父结点比较
// 如果pq[k] >= pq[j]，即父结点大于等于较大子结点时，停止下沉
if (!greater(k, j)) {
break;
}
// 否则交换
swap(k, j);
// 下沉后，下标变成与之交换的元素下标
k = j;
}
}
public static void main(String[] args) {
IndexMinPQ<String> indexMinPQ = new IndexMinPQ<>(20);
indexMinPQ.insert(5, "E");
indexMinPQ.insert(7, "G");
indexMinPQ.insert(2, "B");
indexMinPQ.insert(1, "A");
if (indexMinPQ.contains(7)) {
indexMinPQ.replace(7, "Z");
}
System.out.println(indexMinPQ.min()); // A
System.out.println(indexMinPQ.delMin()); // 1
System.out.println(indexMinPQ.delMin());// 2
System.out.println(indexMinPQ.minIndex()); // 5
System.out.println(indexMinPQ.keyOf(7)); // Z
indexMinPQ.delete(7);
}
}
swap方法不仅交换了pq中的元素——即关联的整数，也要同时更新qp，保持qp[pq[i]] = i这样的关系。swim和sink方法没有改变，要熟知这两个方法操作的是二叉堆pq，而pq中关联的整数映射着真正的数据元素。因此pq[1]存放的是和最小元素关联的整数，通过keys[pq[1]]就可以返回最小元素。这句话解释了min和minIndex方法的实现。
我们来看insert方法，先判断要关联的整数k是不是已经被关联了，没有关联时才能进行下面的操作，和优先队列一样，在二叉堆pq的末尾插入，同时qp数组也要赋值，然后在keys中的关联整数k处存入元素，最后上浮操作恢复堆有序状态；如果整数k已经被关联，即replace方法，用一个新的对象和这个整数关联，这里注意，由于和k关联的新key可能大于原来的key（此时需要下沉），也有可能小于原来的key（此时需要上浮），为了简化代码，既上浮又下沉，就囊括了这两种可能。
delete方法，先找到关联整数k在pq中的位置，然后将其与最后一个交换位置，同时N减去1。之后对换过去的元素作上浮下沉操作，然后才在keys中将k位置的元素置空，一定要先上浮下沉后才置空，因为swim方法没有N的限制，在没有交换元素的情况下，即删除的就是pq中最后一个元素，如果先置空, 会在greater方法中引发空指针。
delMin方法删除最小元素同时返回与之关联的整数。最小元素位于堆顶即pq[1]，这个值就是最小元素关联的整数。之后删除最小元素的操作就和delete类似了，将最小元素的索引pq[1]和最后一个元素交换，然后下沉（在堆顶无需上浮）恢复堆有序状态。
keyOf(int k)返回与整数k关联的元素。
各个方法在最坏情况下的时间复杂度如下所示
可以删除最大元素的IndexMaxPQ
IndexMaxPQ的实现可以通过简单修改IndexMinPQ得到。将greater方法改成less，然后实现中所有greater方法替换成less即可
private boolean less(int i, int j) {
return keys[pq[i]].compareTo(keys[pq[j]]) < 0;
}
实现如下
package Chap9;
import java.util.Arrays;
import java.util.NoSuchElementException;
public class IndexMaxPQ<Key extends Comparable<Key>> {
private int N;
private int[] pq; // 索引二叉堆，按照惯例从1开始
private int[] qp; // 逆序，满足qp[pq[i]] = pq[qp[i]] = i
private Key[] keys;
public IndexMaxPQ(int maxN) {
// 可存放范围为[0, maxN]
keys = (Key[]) new Comparable[maxN + 1];
// 索引二叉堆,存放范围为[1, maxN]
pq = new int[maxN + 1];
// 可存放范围为[0, maxN]
qp = new int[maxN + 1];
// 刚开始没有关联任何整数，都设置为-1
Arrays.fill(qp, -1);
}
// 针对是pq中的索引i、j，但是实际引用的是keys中对应的元素
private boolean less(int i, int j) {
return keys[pq[i]].compareTo(keys[pq[j]]) < 0;
}
public boolean isEmpty() {
return N == 0;
}
public int size() {
return N;
}
public boolean contains(int k) {
return qp[k] != -1;
}
public void insert(int k, Key key) {
if (!contains(k)) {
N++;
pq[N] = k;
qp[k] = N;
keys[k] = key;
swim(N);
}
}
// 给整数k重新关联一个对象
public void replace(int k, Key key) {
keys[k] = key;
// 由于和k关联的新key可能大于原来的key（此时需要下沉），也有可能小于原来的key（此时需要上浮），为了简化代码，既上浮又下沉，就囊括了这两种可能。
swim(qp[k]);
sink(qp[k]);
}
// 返回最小元素
public Key max() {
return keys[pq[1]];
}
// 最小元素的关联整数
public int maxIndex() {
return pq[1];
}
public int delMax() {
if (isEmpty()) {
throw new NoSuchElementException("队列已经为空，不能执行删除！");
}
int indexOfMax = pq[1];
// 堆顶和最后一个元素交换
swap(1, N--);
sink(1);
// 最后一个元素置为空
keys[indexOfMax] = null;
// 同时关联整数pq[N]在pq中的的索引设置为-1，表示还没有对象与该整数关联
qp[indexOfMax] = -1;
return indexOfMax;
}
public void delete(int k) {
if (!contains(k)) {
throw new NoSuchElementException("没有元素与" + k + "关联！");
}
// index为整数k在pq中的位置
int index = qp[k];
swap(index, N--);
// 这里一定要先上浮下沉后再将元素置空，因为swim方法没有N的限制，在没有交换元素的情况下，即删除的就是pq中最后一个元素，如果先置空, 会在greater方法中引发空指针
// 而sink方法有N的限制，先置空后置空都没有影响，2k <= N会限制它进入循环，避免了空指针
swim(index);
sink(index);
keys[k] = null;
qp[k] = -1;
}
public Key keyOf(int k) {
if (contains(k)) {
return keys[k];
}
// 没有与k关联就返回null
return null;
}
private void swap(int i, int j) {
int temp = pq[i];
pq[i] = pq[j];
pq[j] = temp;
// 还要更新qp
qp[pq[i]] = i;
qp[pq[j]] = j;
}
private void swim(int k) {
// k = 1说明当前元素浮到了根结点，它没有父结点可以比较，也不能上浮了，所以k <= 1时候推出循环
while (k > 1 && less(k / 2, k)) {
swap(k / 2, k);
// 上浮后，成为父结点，所以下标变成原父结点
k = k / 2;
}
}
private void sink(int k) {
// 父结点的位置k最大值为 N/2,若k有左子结点无右子结点，那么2k = N；若两个子结点都有，那么2k + 1 = N
// 有可能位置k只有左子结点，依然要比较，用2k + 1 <= N这个的条件不会执行比较，所以用2k <= N条件
while (2 * k <= N) {
int j = 2 * k;
// 可以取j = N -1,greater(N -1, N);由于下标从1开始，所以pq[N]是有元素的
if (j < N && less(j, j + 1)) {
// 右子结点比左子结点大 ，取右子结点的下标
j++;
}
// 左子结点或者右子结点和父结点比较
// 如果pq[k] >= pq[j]，即父结点大于等于较大子结点时，停止下沉
if (!less(k, j)) {
break;
}
// 否则交换
swap(k, j);
// 下沉后，下标变成与之交换的元素下标
k = j;
}
}
public static void main(String[] args) {
IndexMaxPQ<String> indexMaxPQ = new IndexMaxPQ<>(20);
indexMaxPQ.insert(5, "E");
indexMaxPQ.insert(7, "G");
indexMaxPQ.insert(2, "B");
indexMaxPQ.insert(1, "A");
if (indexMaxPQ.contains(7)) {
indexMaxPQ.replace(7, "Z");
}
System.out.println(indexMaxPQ.max()); // Z
System.out.println(indexMaxPQ.delMax()); // 7
System.out.println(indexMaxPQ.delMax());// 5
System.out.println(indexMaxPQ.maxIndex()); // 2
System.out.println(indexMaxPQ.keyOf(1)); // A
indexMaxPQ.delete(1);
}
}
使用优先队列的多项归并
下面的例子使用IndexMinPQ解决了多向归并的问题：它将多个已经有序的输入流归并成一个有序的输出流。无论输入流有多长，都可以将其全部读入并排序（并不是一次性读入内存的，我们将看到任何时刻队列中只存在每个输入流的一个元素而已）
package Chap9;
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
public class Multiway {
public static void merge(InputStream[] streams) throws IOException {
int N = streams.length;
// 为每个输入流关联一个整数
IndexMinPQ<String> pq = new IndexMinPQ<>(N);
// 从每个流中读取一个字符，因为每个流都已经有序，所以其中必然有最小元素
for (int i = 0; i < N; i++) {
int ch;
if ((ch=streams[i].read()) != -1) {
pq.insert(i, String.valueOf((char)ch));
}
}
while (!pq.isEmpty()) {
// 不断选出最小元素打印
System.out.print(pq.min());
// 关联这个整数的对象被删除，从关联该整数的剩余流中再读取一个字符，并加入到索引优先队列中
int i = pq.delMin();
int ch;
if ((ch=streams[i].read()) != -1) {
pq.insert(i, String.valueOf((char)ch));
}
}
System.out.println();
}
public static void main(String[] args) {
InputStream stream1 = new ByteArrayInputStream("ACHYZ".getBytes());
InputStream stream2 = new ByteArrayInputStream("BCRXY".getBytes());
InputStream stream3 = new ByteArrayInputStream("ADPQS".getBytes());
InputStream[] streams = {stream1, stream2 ,stream3};
try {
merge(streams); // AABCCDHPQRSXYYZ
} catch (IOException e) {
e.printStackTrace();
}
}
}
上个例子中有三个输入流，merge方法刚开始给这三个输入流分别关联一个整数，然后从这三个输入流中分别读取一个字符到索引优先队列中。之后就打印三个字符中的最小者，A被打印然后删除，返回与A关联的整数，然后从与该整数关联的剩余流中再读取一个字符，并加入到索引优先队列中。此时的状态又回到每个输入流的元素都有一个存在于索引优先队列中。队列中始终保持只有三个元素，一直选出并删除最小元素，就完成了多向归并排序。
运行上面的代码会输出AABCCDHPQRSXYYZ。将三个序列归并排序成功！对于任意个输入流，merge方法都可以应对，并且队列所需空间和输入流的个数成正比，而不是和所有输入流的元素个数成正比，这可以在归并排序时节约大量内存。
by @sunhaiyu
2017.11.7
