Priority Queue

// File Main.java
public class Main {
  public static void main(String[] args) {
    PriorityQueue<Integer, Integer> q = new PriorityQueue<Integer, Integer>();
    q.insert(10, 1);
    q.insert(40, 4);
    q.insert(50, 5);
    q.insert(200, 20);
    q.insert(70, 7);
    System.out.println("Min priority elem: " + q.extract_min());
    q.decrease_priority(200, 2);
    System.out.println("Min priority elem: " + q.extract_min());
    System.out.println("Min priority elem: " + q.extract_min());
    q.decrease_priority(70, 1);
    System.out.println("Min priority elem: " + q.extract_min());
    System.out.println("Min priority elem: " + q.extract_min());
  }
}

// File PriorityQueue.java
import java.util.HashMap;
import java.util.Vector;

public class PriorityQueue<V, P extends Comparable<P>> {

  private class Elem implements Comparable<Elem> {
    public V value;
    public P priority;
    public int index = -1;

    public Elem(V value, P priority) {
      this.value = value;
      this.priority = priority;
    }
    public int compareTo(Elem arg) {
      return priority.compareTo(arg.priority);
    }
  }

  private class Heap {
    private Vector<Elem> c = new Vector<Elem> ();

    public void push(Elem elem) {
      c.add(elem);
      elem.index = c.size() - 1;
      min_heapify(c.size() - 1);
    }

    public Elem get(int index) {
      return c.get(index);
    }

    public void min_heapify(int index) {
      int q = index;
      int p = (q - 1) / 2;
      while (q != 0 && c.get(p).compareTo(c.get(q)) > 0) {
        Elem tmp = c.get(p);
        c.set(p, c.get(q)); c.get(p).index = p;
        c.set(q, tmp); c.get(q).index = q;
        q = p;
        p = (q - 1) / 2;
      }
    }

    public Elem pop() {
      Elem tmp = c.firstElement();
      c.set(0, c.get(c.size() - 1)); c.get(0).index = 0;
      c.remove(c.size() - 1);
      int n = c.size() - 1;
      int p = 0;
      int g = 1;
      int d = 2;
      while (true) {
        if (d <= n && (c.get(d).compareTo(c.get(g)) <= 0 && c.get(d).compareTo(c.get(p)) < 0)) {
          Elem tmp2 = c.get(p);
          c.set(p, c.get(d)); c.get(p).index = p;
          c.set(d, tmp2); c.get(d).index = d;
          p = d; g = 2 * p + 1; d = g + 1;
        }
        else if ((d == n + 1 && c.get(g).compareTo(c.get(p)) < 0) ||
                 (d <= n && (c.get(g).compareTo(c.get(p)) < 0 &&
                       c.get(g).compareTo(c.get(d)) <= 0))) {
          Elem tmp2 = c.get(p);
          c.set(p, c.get(g)); c.get(p).index = p;
          c.set(g, tmp2); c.get(g).index = g;
          p = g; g = 2 * p + 1; d = g + 1;
        }
        else break;
      }
      return tmp;
    }
  }

  private Heap h = new Heap();
  private HashMap<V, Elem> hm = new HashMap<V, Elem>();

  public void insert(V value, P priority) {
    Elem elem = new Elem(value, priority);
    h.push(elem);
    hm.put(value, elem);
  }

  public V extract_min() {
    Elem elem = h.pop();
    hm.remove(elem.value);
    return elem.value;
  }

  public void decrease_priority(V value, P priority) {
    int index = hm.get(value).index;
    h.get(index).priority = priority;
    h.min_heapify(index);
  }
}

/*
$ javac PriorityQueue.java
$ javac Main.java
$ java Main
Min priority elem: 10
Min priority elem: 200
Min priority elem: 40
Min priority elem: 70
Min priority elem: 50
*/