在开始讲“Index min priority queue”之前，我们需要先了解以下一些概念：
Complete Binary Tree:
A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible
Binary Heap:
The binary heap is a data structure that can efficiently support the basic priority-queue operations. In a binary heap, the items are stored in an array such that each key is guaranteed to be larger than (or equal to) the keys at two other specific positions
A binary heap is a set of nodes with keys arranged in a complete heap-ordered binary tree, represented in level order in an array (not using the first entry).
In a heap, the parent of the node in position k is in position k/2; and, conversely, the two children of the node in position k are in positions 2k and 2k + 1.
Algorithms on heaps:
We represent a heap of size n in private array pq[] of length n + 1, with pq[0] unused and the heap in pq[1] through pq[n].
- Bottom-up reheapify (swim): If the heap order is violated because a node’s key becomes larger than that node’s parents key, then we can make progress toward fixing the violation by exchanging the node with its parent. After the exchange, the node is larger than both its children (one is the old parent, and the other is smaller than the old parent because it was a child of that node) but the node may still be larger than its parent. We can fix that violation in the same way, and so forth, moving up the heap until we reach a node with a larger key, or the root. Bottom-up heapify (swim)
private void swim(int k) {
while (k > 1 && less(k/2, k)) {
exch(k, k/2);
k = k/2;
}
}- Top-down heapify (sink): If the heap order is violated because a node’s key becomes smaller than one or both of that node’s children’s keys, then we can make progress toward fixing the violation by exchanging the node with the larger of its two children. This switch may cause a violation at the child; we fix that violation in the same way, and so forth, moving down the heap until we reach a node with both children smaller, or the bottom
private void sink(int k) {
while (2*k <= N) {
int j = 2*k;
if (j < N && less(j, j+1)) j++;
if (!less(k, j)) break;
exch(k, j);
k = j;
}
}
Heap-based priority queue:
- Insert: We add the new item at the end of the array, increment the size of the heap, and then swim up through the heap with that item to restore the heap condition.
- Remove the maximum: We take the largest item off the top, put the item from the end of the heap at the top, decrement the size of the heap, and then sink down through the heap with that item to restore the heap condition.
In an n-item priority queue, the heap algorithms require no more than 1 + lg n compares for insert and no more than 2 lg n compares for remove the maximum.
了解了上面的概念，“Index min priority queue” 就很容易实现了。具体的概念、接口和代码如下。
Index priority queue:
In many applications, it makes sense to allow clients to refer to items that are already on the priority queue. One easy way to do so is to associate a unique integer index with each item.
import java.util.Iterator;
import java.util.NoSuchElementException;
public class IndexMinPQ<Key extends Comparable<Key>> implements Iterable<Integer>{
private int maxN; // maximum number of elements on PQ
private int n; // number of elements on PQ
private int[] pq; // binary heap using 1-based indexing
private int[] qp; //inverse of pq: qp[pq[i]] = pq[qp[i]] = i
private Key[] keys;
public IndexMinPQ(int maxN){
if(maxN < 0) throw new IllegalArgumentException();
this.maxN = maxN;
n = 0;
keys = (Key[]) new Comparable[maxN + 1];
pq = new int[maxN + 1];
qp = new int[maxN + 1];
for (int i = 0; i < maxN + 1; i++) {
qp[i] = -1;
}
}
public boolean isEmpty(){
return n == 0;
}
public boolean contains(int i){
if(i < 0 || i >= maxN) throw new IllegalArgumentException();
return qp[i] != -1;
}
public int size(){
return n;
}
public void insert(int i, Key key){
if(contains(i)) throw new IllegalArgumentException("index " + i + " is already in priority queue");
n++;
keys[i] = key;
pq[n] = i;
qp[i] = n;
swim(n);
}
public int delMin(){
if(n == 0) throw new NoSuchElementException("Priority queue underflow");
int min = pq[1];
exch(1, n--);
sink(1);
pq[n+1] = -1;
keys[min] = null;
qp[min] = -1;
return min;
}
public void decreaseKey(int i, Key key){
if(!contains(i)) throw new IllegalArgumentException("index is not in the priority queue");
if(keys[i].compareTo(key) <= 0) throw new IllegalArgumentException("Calling decreaseKey() with given argument would not strictly decrease the key");
keys[i] = key;
swim(qp[i]);
}
public void increaseKey(int i, Key key) {
if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
if (keys[i].compareTo(key) >= 0)
throw new IllegalArgumentException("Calling increaseKey() with given argument would not strictly increase the key");
keys[i] = key;
sink(qp[i]);
}
private void swim(int k){
while(k > 1 && greater(k/2, k)){
exch(k, k/2);
k = k/2;
}
}
private void sink(int k){
while(2 * k <= n ){
k = 2*k;
if(k < n && greater(k, k + 1)) k = k + 1;
if(!greater(k/2, k)) break;
exch(k, k/2);
}
}
private boolean greater(int i, int j){
return keys[pq[i]].compareTo(keys[pq[j]]) > 0;
}
private void exch(int i, int j){
int tmp = pq[i];
pq[i] = pq[j];
pq[j] = tmp;
qp[pq[i]] = i;
qp[pq[j]] = j;
}
public Iterator<Integer> iterator(){
return new HeapIterator();
}
private class HeapIterator implements Iterator<Integer>{
private IndexMinPQ<Key> copy;
public HeapIterator(){
copy = new IndexMinPQ<>(pq.length - 1);
for (int i = 1; i <= n; i++) {
copy.insert(pq[i], keys[pq[i]]);
}
}
public boolean hasNext(){
return !copy.isEmpty();
}
public void remove(){
throw new UnsupportedOperationException();
}
public Integer next(){
if(!hasNext()) throw new NoSuchElementException();
return copy.delMin();
}
}
public static void main(String[] args) {
// insert a bunch of strings
String[] strings = { "it", "was", "the", "best", "of", "times", "it", "was", "the", "worst" };
IndexMinPQ<String> pq = new IndexMinPQ<String>(strings.length);
for (int i = 0; i < strings.length; i++) {
pq.insert(i, strings[i]);
}
// delete and print each key
while (!pq.isEmpty()) {
int i = pq.delMin();
System.out.println(i + " " + strings[i]);
}
System.out.println();
// reinsert the same strings
for (int i = 0; i < strings.length; i++) {
pq.insert(i, strings[i]);
}
// print each key using the iterator
for (int i : pq) {
System.out.println(i + " " + strings[i]);
}
while (!pq.isEmpty()) {
pq.delMin();
}
}
}