It is a priority queue sorted by Key (Key extends Comparable<Key>):
int delMin(); <-- delete the one which has lowest priority
It supports indexed insert, update and delete:
void insert(int i, Key key);
void increaseKey(int i, Key key);
void decreaseKey(int i, Key key);
void delete(int); <-- delete the one on position i regardless its priority
All operations are log V or less.
It is used by:
1. Eager Prim MST (minimal spanning tree)
2. Dijkstra's shortest path algorithm
Invariables to keep in mind when dealing with IndexMinPQ:
1. Priority is stored in Key[]
2. Vertex is stored in pq[] -- this is the real priority queue
3. Using qp[] to reverse lookup from vertex id to its entry in pq[], i.e. pq[qp[i]] == i.
We can use 'delete' to see their relationships:
/**
* Remove vertex i (stored in pq[]) and its priority (stored in keys[]).
* @param i the vertex id
*/
public void delete(int i) {
if (i < 0 || i >= NMAX) throw new IndexOutOfBoundsException();
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;
}
Both sink and swim are modified to use priority values stored in Key[] to change the order of priority queue:
private void swim(int k) {
while (k > 1 && greater(k/2, k) {
exch(k, k/2);
k = k/2;
}
}
private boolean greater(int i, int j) {
return keys[pq[i]].compareTo(keys[pq[j]]) > 0;
}
