一个支持删除最大元素和插入元素操作的数据结构，叫优先队列。
我们可以用无序数组（插入O(1)， 删除最大O(n)），有序数组（插入O(n), 删除最大O(1)），堆（插入O(logn)， 删除最大O(logn)）
这里的堆指的是二叉堆。
二叉堆的定义：二叉堆是一组能够用堆有序的完全二叉树排序的元素，并在数组中按照层级储存（不使用数组的第一个元素）。
堆有序：一课二叉树的每个节点都大于等于他的两个子节点
完全二叉树：除了最后一层外的其他每一层都 都被完全填充，最后一层向左对齐。
一个二叉堆数组
下面来看基于堆的优先队列的实现：
public class MaxPQ<Key extends Comparable<Key>> {
private int n;
private Key[] keys;
public MaxPQ(int capacity) {
// TODO Auto-generated constructor stub
keys = (Key[]) new Comparable[capacity+1];
n = 0;
}
private boolean less(int i, int j) {
return keys[i].compareTo(keys[j]) < 0;
}
private void exch(int i, int j) {
Key temp = keys[i];
keys[i] = keys[j];
keys[j] = temp;
}
private void swim(int k) {
while (k > 1 && less(k/2, k)) {
exch(k/2, k);
k /= 2;
}
}
private void sink(int k) {
while (k*2 <= n) {
int j = k*2;
//注意这里j < n，删除最大值操作时n+1位为被剔除的最大值
if (j < n && less(j, j+1)) j++;
if (less(k, j)) break;
exch(k, j);
k = j;
}
}
private void resize(int newCapacity) {
Key[] copy = (Key[]) new Comparable[newCapacity];
for(int i = 1; i <= n; i++) {
copy[i] = keys[i];
}
keys = copy;
}
public void insert(Key key) {
if (n == keys.length-1) resize(2*keys.length);
keys[++n] = key;
swim(n);
}
public Key delMax() {
Key max = keys[1];
exch(1, n--);
sink(1);
keys[n+1] = null;
if ((n > 0) && (n == (keys.length-1)/4)) resize(keys.length/2);
return max;
}
}
我们抽象出了这样一种数据结构的目的就是让插入，删除最大操作都为O(logn。当插入一个元素的时候，把他放数组末尾k，然后不断与他的上一层就是k/2比较交换，直到满足定义。当要删除最大数时，先把数组第一位与最后以为交换，然后让这个新头元素不断与下层比较交换。
下面来介绍索引优先队列：就是给优先队列里的每个元素一个索引，可以理解为通过此来拓展优先队列的功能，支持更多操作
/**
* 索引优先队列，在原先基于堆的优先序列上对每个元素增加了索引，可以看成是功能的拓展
* 比如通过索引改变某个值，或是删除某个值，这些操作复杂度都是log(n)
* @author Administrator
*
* @param <Key>
*/
public class IndexMaxPQ<Key extends Comparable<Key>> {
private Key[] keys;
private int[] pq; //存储索引的数组
private int[] qp; //qp[pq[i]] = i;
private int n;
public IndexMaxPQ(int maxN) {
// TODO Auto-generated constructor stub
keys = (Key[]) new Comparable[maxN + 1];
pq= new int[maxN + 1];
qp = new int[maxN+1];
for (int i = 0; i <=maxN; i++) {
qp[i] = -1;
}
}
/**
* 交换pq[i]与pq[j]
* @param i
* @param j
*/
private void exch(int i, int j) {
int temp = pq[i];
pq[i] = pq[j];
pq[j] = temp;
qp[pq[i]] = i;
qp[pq[j]] = j;
}
private boolean less(int i, int j) {
return keys[pq[i]].compareTo(keys[pq[j]]) < 0;
}
private void swim(int k) {
while (k/2 >= 1 && less(k/2, k)) {
exch(k, k/2);
k /= 2;
}
}
private void sink(int k) {
while (k*2 <= n) {
int j = k*2;
if (j < n && less(j, j+1)) j++; // j<n这步判断很重要，在删除最大数的时候不再将被替换到末尾的索引考虑在内
if (less(j, k)) break;
exch(j, k);
k = j;
}
}
public boolean isEmpty() {
return n==0;
}
public int size() {
return n;
}
/**
* 是否包含该索引
* @param i
* @return
*/
public boolean contains(int i) {
return qp[i] != -1;
}
/**
* 插入
* @param i 索引值
* @param key 插入值
*/
public void insert(int i, Key key) {
if (contains(i))
throw new IllegalArgumentException("index is already in the priority queue");
n++;
pq[n] = i;
qp[i] = n;
keys[i] = key;
swim(n);
}
public int maxIndex() {
if (n == 0) throw new NoSuchElementException("priority queue underFlow");
return pq[1];
}
public Key maxKey() {
if (n == 0) throw new NoSuchElementException("priority queue underFlow");
return keys[pq[1]];
}
/**
* 删除最大值
* @return 返回被删除的最大值的索引
*/
public int delMax() {
if (n == 0) throw new NoSuchElementException("priority queue underFlow");
int maxIndex = pq[1];
exch(1, n--);
sink(1);
assert pq[n+1] == maxIndex ;
keys[maxIndex ] = null;
pq[n+1] = -1;
qp[maxIndex ] = -1;
return maxIndex ;
}
/**
* 通过索引来更改key
* @param i 索引
* @param key 要被更改的值
*/
public void changeKey(int i, Key key) {
if (!contains(i))
throw new NoSuchElementException("index is not in the priority queue");
keys[i] = key;
swim(qp[i]);
sink(qp[i]);
}
/**
* 删除索引为i的key
* @param i
*/
public void delete(int i) {
if (!contains(i))
throw new NoSuchElementException("index is not in the priority queue");
int index = qp[i];
exch(index, n--);
swim(index);
sink(index);
keys[i] = null;
qp[i] = -1;
}
}
实现思想是，keys[]数组在i指针处存放key，不对它做任何排序操作；pq[]数组从1开始在++n处存放指针i，然后进行堆排序形成二叉堆，这样透过指针的key就堆有序了；qp[]数组qp[pq[k]] = k，以指针为下标存放该指针在pq[]数组中的下标。
