Heap.java

import java.util.ArrayList;
import java.util.HashMap;

public class Heap<T extends Comparable<T>> {
    ArrayList<T> data = new ArrayList<>();
    HashMap<T, Integer> map = new HashMap<>();

    public void add(T item) {
        data.add(item);
        map.put(item, this.data.size() - 1);
        upheapify(data.size() - 1);
    }

    private void upheapify(int ci) {
        int pi = (ci - 1) / 2;
        if (isLarger(data.get(ci), data.get(pi)) > 0) {
            swap(pi, ci);
            upheapify(pi);
        }
    }

    private void swap(int i, int j) {
        T ith = data.get(i);
        T jth = data.get(j);

        data.set(i, jth);
        data.set(j, ith);
        map.put(ith, j);
        map.put(jth, i);
    }

    public void display() {
        System.out.println(data);
    }

    public int size() {
        return this.data.size();
    }

    public boolean isEmpty() {
        return this.size() == 0;
    }

    public T remove() {
        swap(0, this.data.size() - 1);
        T rv = this.data.remove(this.data.size() - 1);
        downheapify(0);

        map.remove(rv);
        return rv;
    }

    private void downheapify(int pi) {
        int lci = 2 * pi + 1;
        int rci = 2 * pi + 2;
        int mini = pi;

        if (lci < this.data.size() && isLarger(data.get(lci), data.get(mini)) > 0) {
            mini = lci;
        }

        if (rci < this.data.size() && isLarger(data.get(rci), data.get(mini)) > 0) {
            mini = rci;
        }

        if (mini != pi) {
            swap(mini, pi);
            downheapify(mini);
        }
    }

    public T get() {
        return this.data.get(0);
    }

    public int isLarger(T t, T o) {
        return t.compareTo(o);
    }

    public void updatePriority(T pair) {
        int index = map.get(pair);
        upheapify(index);
    }
}