java用数组实现最小堆

public class BinaryHeap {

    private static final int DEFAULT_CAPACITY = 10;     //默认容量
    private int[] array;    //底层结构
    private int currentSize;    //当前存放的元素个数

    /*
    无参构造
     */
    public BinaryHeap() {
        array = new int[DEFAULT_CAPACITY];
    }

    /*
    带初始容量的构造
     */
    public BinaryHeap(int capacity) {
        array = new int[(capacity + 2) * 11 / 10];
    }

    /*
    传入初始数组的构造器
     */
    public BinaryHeap(int[] nums) {
        currentSize = nums.length;
        array = new int[currentSize + 1];
        int i = 1;
        for (int num : nums) {
            array[i++] = num;
        }
        buildHeap();
    }

    /*
    建堆
     */
    private void buildHeap() {
        for (int i = currentSize / 2; i > 0 ; i--) {
            percolateDown(i);
        }
    }

    /*
    建堆过程
     */
    private void percolateDown(int hole) {
        int child;
        int tmp = array[hole];
        for (; hole * 2 <= currentSize; hole = child) {
            child = hole * 2;
            if (child != currentSize && array[child] > array[child + 1]) {
                child++;
            }
            if (array[child] < tmp) {
                array[hole] = array[child];
            } else {
                break;
            }
        }
        array[hole] = tmp;
    }

    /*
    确保容量，每次添加元素之前调用
     */
    private void ensureCapacity() {
        int[] old = array;
        int newLen = old.length * 2 ;
        array = new int[newLen];
        for (int i = 0; i < old.length; i++) {
            array[i] = old[i];
        }
    }

    /*
    判断堆是否为空
     */
    public boolean isEmpty() {
        return currentSize == 0;
    }

    /*
    插入元素
     */
    public void insert(int x) {
        if(currentSize == array.length - 1){
            ensureCapacity();
        }
        int hole = ++currentSize;
        for( ; array[hole / 2] > x && hole > 1; hole /= 2){
            array[hole] = array[hole / 2];
        }
        array[hole] = x;
    }

    /*
    查找最小元素，如果堆不为空，则返回堆顶元素，即array[1]
     */
    public int findMin() {
        if(currentSize == 0){
            throw new BufferUnderflowException();
        }
        return array[1];
    }

    /*
    删除最小元素
     */
    public int deleteMin(){
        int minItem = findMin();
        array[1] = array[currentSize--];
        percolateDown(1);
        return minItem;
    }

    @Override
    public String toString() {
        return "BinaryHeap{" +
                "array=" + Arrays.toString(array) +
                '}';
    }

    /*
    清空堆，把所有元素置为零，堆内元素的个数置为0
     */
    public void clear(){
        int len = array.length;
        array = new int[len];
        currentSize = 0;
    }
}