/*
*
* Indexed Priority Queue.
* supports change node i's priority keys[i] and delete node i.
* time: O(NlogN)
* space: O(N)
*/
public class IndexMinPQ<Key extends Comparable<Key>> {
public static int[] arr = {3, 2, 4, 1, 8, 5, 0};
private int N; //number of elements on PQ
private int[] pq; //binary heap using 1-based indexing
private int[] qp; //inverse: qp[pq[i]] = pq[qp[i]] = i
private Key[] keys; //items with priorities
public IndexMinPQ(int maxN) {
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;
}
public boolean isEmpty() {
return N == 0;
}
public boolean contains(int k) {
return qp[k] != -1;
}
public void insert(int k, Key key) {
N++;
qp[k] = N;
pq[N] = k;
keys[k] = key;
swim(N);
}
public Key min() {
return keys[pq[1]];
}
public int delMin() {
int indexOfMin = pq[1];
exch(1, N--);
sink(1);
keys[pq[N+1]] = null;
qp[pq[N+1]] = -1;
return indexOfMin;
}
public int minIndex() {
return pq[1];
}
public void change(int k, Key key) {
keys[k] = key;
swim(qp[k]);
sink(qp[k]);
}
public void delete(int k) {
exch(k, N--);
swim(qp[k]);
sink(qp[k]);
keys[pq[N+1]] = null;
qp[pq[N+1]] = -1;
}
private void sink(int k) {
while(2*k <= N) {
int j = 2*k;
if(j < N && greater(keys[pq[j]], keys[pq[j+1]])) j++;
if(!greater(keys[pq[k]], keys[pq[j]])) break;
exch(k, j);
k = j;
}
}
private void swim(int k) {
while(k > 1 && greater(keys[pq[k/2]], keys[pq[k]])) {
exch(k/2, k);
k = k/2;
}
}
private void exch(int i, int j) {
Key tmp = keys[pq[i]];
keys[pq[i]] = keys[pq[j]];
keys[pq[j]] = tmp;
}
private boolean greater(Key key1, Key key2) {
return key1.compareTo(key2) > 0;
}
public static void main(String[] args) {
IndexMinPQ<Integer> impq = new IndexMinPQ<Integer>(arr.length);
for (int i = 0; i < arr.length; i++) {
impq.insert(i+1, new Integer(arr[i])); //in graph, i is node (skip 0), arr[i] is shortest path to node i
}
while(!impq.isEmpty()) {
System.out.println(impq.min());
int minIndex = impq.delMin();
//System.out.println("delMin Index: " + minIndex);
}
System.out.println("change index 2 to 1000");
for (int i = 0; i < arr.length; i++) {
impq.insert(i+1, new Integer(arr[i]));
}
// printArray(impq);
System.out.println(impq.contains(2));
impq.change(2, 10000);
// printArray(impq);
while(!impq.isEmpty()) {
System.out.println(impq.min());
int minIndex = impq.delMin();
// System.out.println("delMin Index: " + minIndex);
// printArray(impq);
}
System.out.println("delete key at index 2");
for (int i = 0; i < arr.length; i++) {
impq.insert(i+1, new Integer(arr[i]));
}
System.out.println(impq.contains(2));
impq.delete(2);
while(!impq.isEmpty()) {
System.out.println(impq.min());
int minIndex = impq.delMin();
//System.out.println("delMin Index: " + minIndex);
}
}
public static void printArray(IndexMinPQ impq) {
System.out.println("====================");
System.out.println("pq:");
for(int i = 0; i < impq.pq.length; i++) {
System.out.print("pq[" + i + "] = " + impq.pq[i] + ",");
}
System.out.println("qp:");
for(int i = 0; i < impq.qp.length; i++) {
System.out.print("qp[" + i + "] = " + impq.qp[i] + ",");
}
System.out.println("keys:");
for(int i = 0; i < impq.keys.length; i++) {
System.out.print("keys[" + i + "] = " + impq.keys[i] + ",");
}
System.out.println("====================");
}
}
