索引优先队列的实现

注：此文需要对有序二叉堆、优先队列等知识有所了解，建议看完用有序二叉堆实现优先队列后再阅读此文

背景

普通优先队列（不带索引）只能访问有序二叉堆的根节点，而无法引用队列中的其它任何元素。

特点

索引优先队列中存储的元素都有对应的“索引”，通过“索引”我们可以引用该索引对应的元素。可以理解为HashMap中的key-value，key即索引，value即所对应的元素。

实现要点

数组T[] a存放所有的元素，数组的下标对应该元素的索引，元素在该数组中是无序的。数组int[] pq 存放所有元素的索引，pq要实现为优先队列（即有序二叉堆的结构），索引在pq中是有序的数组int[] qp是pq的“倒置”数组，下标为元素的索引，若pq[i] = k，则pq[k] = i。默认情况下存放-1，此数组用来通过索引拿到在二叉堆（pq）中的节点位置。

代码实现

public class IndexMaxPQ<T extends Comparable<T>>{ private int N = 0;//队列大小 private int index = 0;//队列中元素个数 private T[] a;//存放元素 private int[] pq;//存放索引 private int[] qp;//存放索引在pq中的下标，索引不存在的话为-1 public IndexMaxPQ(int size){ N = size; for(int i = 0; i < N; i++){ qp[i] = -1; }//qp全部初始化为-1 a = (T[])new Comparable<T>(N + 1); pq = new int[](N + 1); qp = new int[](N + 1); } public void insert(int k, T item){ if (contains(k)) { throw new IllegalArgumentException("index is already in the priority queue"); } a[k] = item;//保存元素 pq[++index] = k;//保存索引在二叉堆末尾 qp[k] = index;//保存索引对应的二叉堆节点位置（暂时在末尾，在swim中会更新节点位置） swim(index);//上浮至正确节点 } public boolean contains(int k){ return qp[k] != -1;//-1表明索引没有对应的节点位置 } public void delete(int k){ int j = qp[k];//通过索引取出节点位置 pq[j] = pq[index];//用末尾节点覆盖当前节点 pq[index] = null;//末尾节点置null sink(j);//下沉至正确节点位置 qp[k] = -1;//索引被删除，相当于二叉堆中无此节点位置 a[k] = null;//元素置null index--; } public T delMax(){ T max = a[pq[1]]; int k = pq[1]; a[k] = null; pq[1] = pq[index--]; sink(1); qp[k] = -1; return T; } //上浮动作，可参考[用有序二叉堆实现优先队列](http://blog.csdn.net/a854702872/article/details/77687288) private void swim(int j){ while (j > 1) { if (a[pq[j/2]] < a[pq[j]]) {//注意比较的是索引对应的元素，即a[]中的值 swap(j/2, j); j = j / 2; } else{ break; } } } private void swap(int m, int n){ int iTemp = pq[m]; pq[m] = pq[n]; pq[n] = iTemp ;//交换索引 qp[pq[m]] = m;//索引对应的节点位置更新 qp[pq[n]] = n; } //下沉动作，可参考[用有序二叉堆实现优先队列](http://blog.csdn.net/a854702872/article/details/77687288) private void sink(int j){ while (j * 2 < N) { int m = j * 2; if (a[pq[m]] < a[pq[m++]]) {m++;} if (a[pq[j]] > a[pq[m]]) {break;} swap(j, m); j = m; } } }