public class Heap<T extends Comparable<T>>{
    //存储堆中的元素
    private T[] items;
    private int N;
 
    public Heap(int capacity){
        this.items = (T[]) new Comparable[capacity+1]; //因为数组下标0没有使用
        this.N = 0;
    }
 
    //判断堆中索引i处的元素是否小于索引j处的元素
    private boolean less(int i, int j){
        return items[i].compareTo(items[j])<0;
    }
    // 交换堆中i索引和j索引处的值
    private void exch(int i, int j){
        T temp = items[i];
        items[i] = items[j];
        items[j] = temp;
    }
    // 往堆中插入一个元素
    public void insert(T t){
        //因为一开始N=0，这样第一个插入的元素就在items[1]，
        items[++N]=t;
        //需要调整元素位置，让堆有序（每个结点都大于其两个子结点）
        swim(N);
    }
    // 使用上浮算法，使索引k处的元素能在堆中处于一个正确的位置
    // 不断和父节点比较
    private void swim(int k){
        //如果父节点的值比当前结点的值小，则交换位置
        while(k>1){
            if(less(k/2,k)){
                exch(k/2,k);
            }else{
                break;
            }
            k = k/2;
        }
    }
 
    // 删除堆中最大的元素，并返回这个最大元素
    public T delMax(){
        //删除最大元素，其实就是删除根结点
        T max = items[1];
        //交换到索引结尾处
        exch(1, N);
        items[N]=null;
        N--;
        sink(1);
        return max;
    }
 
    // 使用下沉算法，使索引k处的元素能在堆中处于一个正确的位置
    // 当前节点a[k]和它的子节点a[2k]和a[2k+1]中较大者交换位置
    private void sink(int k){
        //循环条件：有子节点
        while(2*k<=N){
            int max; //暂存较大的子节点
            //<=N 说明存在叶子节点
            if (2*k+1<=N){
                if(less(2*k,2*k+1)){
                    max = 2*k + 1;
                }else{
                    max = 2*k;
                }
            }else{
                max = 2*k;
            }
            if(!less(k,max)){
                break;
            }
            exch(k,max);
 
            //变化k的值
            k = max; //下一次循环
        }
    }
}