public class MaxBinaryHeap<T extends Comparable<T>> {
    private final T[] array;

    private int lastIndex = 0;

    public MaxBinaryHeap(int size) {
        this.array = (T[]) new Comparable[size + 1];
    }

    private int parent(int root) {
        return root / 2;
    }

    private int left(int root) {
        return root * 2;
    }

    private int right(int root) {
        return root * 2 + 1;
    }

    private void exchange(int fir, int sec) {
        T temp = array[sec];
        array[sec] = array[fir];
        array[fir] = temp;
    }

    private boolean less(int fir, int sec) {
        return array[fir].compareTo(array[sec]) < 0;
    }

    public T Max() {
        return array[1];
    }

    //元素上浮，直到父节点大于自己
    private void up(int k) {
        while (k > 1 && less(parent(k), k)) {
            //如果k比k的父节点大,则上升
            exchange(parent(k), k);
            k = parent(k);
        }
    }

    //元素下沉，直到子节点小于自己
    private void down(int k) {
        //是否存在左节点
        while (left(k) <= lastIndex) {
            int older = left(k);
            if (right(k) <= lastIndex) {
                older = less(left(k), right(k)) ? right(k) : left(k);
            }
            //如果k比子节点大,则不用下沉
            if (less(older, k)) break;
            exchange(older, k);
            k = older;
        }
    }

    //在数组末尾插入元素，并将元素上浮到合适的位置
    public void insert(T item) {
        array[++lastIndex] = item;
        up(lastIndex);
    }

    //删除数组中最大的元素，并调整位置
    public T PopMax() {
        T res = Max();
        exchange(1, lastIndex);
        array[lastIndex--] = null;
        down(1);
        return res;
    }
}