（JAVA）浅入数据结构 “堆” - 实现和理论

package com.renexdemo.heap;

// 堆
public class Heap<T extends Comparable<T>> {
    private T[] items;
    private int N;

    // 初始化构造
    public Heap(int capacity) {
        this.items = (T[]) new Comparable[capacity+1];
        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 T delMax(){
        T max = items[1];

        // 交换元素，让完全二叉树最右侧的元素变为临时根节点
        exch(1,N);

        // 最大索引处的元素删除掉
        items[N] = null;

        // 元素个数-1
        N--;

        // 对堆重新排序
        sink(1);

        return max;
    }

    // 往堆中插入一个元素
    public void insert(T t){
        items[++N] = t;
        swim(N);
    }

    //上浮算法
    private void swim(int k){
        // 通过循环，不断的比较当前节点的值和父节点的值，如果发现父节点的值比当前节点的值小，则交换位置
        while (k>1){
            // 比较当前节点和父节点
            if (less(k/2,k)){
                exch(k/2,k);
            }
            k = k/2;
        }
    }

    // 下沉算法
    private void sink(int k){
        // 通过循环不断的对比当前k节点和其子节点2*k以及2k+1的元素大小，如果当前节点小，则需要交换位置

        // 若是左子节点大于最大索引，那么结束循环
        while (2*k<=N){
            // 获取当前节点的子节点的较大节点
            int max;// 记录较大节点所在的索引

            // 比较最大值
            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;
            }

            // 交换k索引处的值和max索引处的值
            exch(k,max);

            // 变换k的值
            k = max;

        }

    }
}