Heap

public class Heap <T>{

    private int capacity = 0;
    private T[] buffer;
    private int size;
    private Comparator<T> comparator;

    public Heap(int capacity, Comparator<T> comparator) {
        this.comparator = comparator;
        this.capacity = capacity;
        this.buffer = (T[])new Object[this.capacity + 1]; // spare buffer[0]
    }

    public Heap(T[] buffer, Comparator<T> comparator) {
        this.comparator = comparator;
        this.capacity = buffer.length * 2; // spare buffer[0]
        this.size = buffer.length;
        this.buffer = (T[])new Object[this.capacity + 1];
        for(int i = 0; i < buffer.length; i ++)
            this.buffer[i+1] = buffer[i]; // buffer[0] is not used

        int nonLeafNodeIndex = this.size / 2; // the last
        for(int i = nonLeafNodeIndex; i >= 1; i --)
            this.swim(i);
    }

    public void insert(T value) {
        if(this.size >= this.capacity) { // resize
            this.capacity *= 2;
            T[] buffer = (T[])new Object[this.capacity + 1];
            for(int i = 1; i <= this.size; i ++) {
                buffer[i] = this.buffer[i];
            }
            this.buffer = buffer;
        }
        this.buffer[++size] = value;
        this.swim(size/2);
    }

    public T remove() {
        T top = this.buffer[1];
        this.buffer[1] = this.buffer[this.size--];
        this.sink(1);
        return top;
    }

    public void sink(int index) {
        while(index <= this.size/2) { // loop until last non leaf child
            // Compare the left and right child
            // to see which one should be exchanged with current node
            int exchangeChildIndex = 2 * index;
            T exchangeChild = this.buffer[2 * index];
            if(2 * index + 1 <= this.size) {
                if(this.comparator.compare(exchangeChild, this.buffer[2 * index + 1]) < 0) {
                    exchangeChildIndex = 2 * index + 1;
                    exchangeChild = this.buffer[exchangeChildIndex];
                }
            }

            if(this.comparator.compare(this.buffer[index], exchangeChild) >= 0)  // heap condition met
                break;
            else {
                this.swap(this.buffer, index, exchangeChildIndex);
                index = exchangeChildIndex;
            }
        }
    }

    public void swim(int index) {
        while(index >= 1 && 2 * index <= this.size) { // loop until first node
            // Compare the left and right child
            // to see which one should be exchanged with current node
            int exchangeChildIndex = 2 * index;
            T exchangeChild = this.buffer[2 * index];
            if(2 * index + 1 <= this.size) {
                if(this.comparator.compare(exchangeChild, this.buffer[2 * index + 1]) < 0) {
                    exchangeChildIndex = 2 * index + 1;
                    exchangeChild = this.buffer[exchangeChildIndex];
                }
            }

            if(this.comparator.compare(this.buffer[index], exchangeChild) >= 0)  // heap condition met
                break;
            else {
                this.swap(this.buffer, index, exchangeChildIndex);
                index /= 2;
            }
        }
    }

    private void swap(T[] array, int i, int j) {
        T tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

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