优先队列（堆）

public class BinaryHeap<T extends Comparable<? super T>> {

    private static final int DEFAULT_CAPACITY = 10;

    /**
     * 当前堆中的元素数量
     */
    private int currentSize;
    /**
     * 存储堆的数组
     */
    private T[] array;

    /**
     * Construct the binary heap.
     */
    public BinaryHeap() {
        // 调用本类的另一个构造方法
        this(DEFAULT_CAPACITY);
    }

    public BinaryHeap(int capacity) {
        currentSize = 0;
        // 堆数组的0的位置是不使用的，所以长度需要加1
        array = (T[]) new Comparable[capacity + 1];
    }

    /**
     * 使用数组建堆
     */
    public BinaryHeap(T[] items) {
        currentSize = items.length;
        // 开辟空间数组
        array = (T[]) new Comparable[(currentSize + 2) * 11 / 10];
        int i = 1;
        // 初始化堆数组
        for (T item : items) {
            array[i++] = item;
        }
        buildHeap();
    }

    private void buildHeap() {
        for (int i = currentSize / 2; i > 0; i--) {
            // 循环遍历来xia'fu'shen'sh
            percolateDown(i);
        }
    }

    public void insert(T x) {
        if (currentSize == array.length - 1) {
            // 下标0不用，所以需要减去1
            // 2倍扩容，同时可以使用的空间为2的倍数个
            this.enlargeArray(array.length * 2 + 1);
        }
        // 将X上冒到正确的位置
        currentSize++;
        // 空节点下标
        int hole = currentSize;
        // 先将x存到下标0的位置（该位置不使用），hole = hole / 2：意思是访问hole的父节点，空节点上冒
        for (array[0] = x; x.compareTo(array[hole / 2]) < 0; hole /= 2) {
            // 理解的为x在空节点hole处，
            // x.compareTo(array[hole / 2]) < 0 ： x小于父节点的元素。将父节点的值下浮到空节点（等同于将空节点上冒到父节点）
            array[hole] = array[hole / 2];
        }
        array[hole] = x;
    }

    public T deleteMin() {
        // 堆为空
        if (currentSize == 0) {
            throw new RuntimeException();
        }
        // 最小的元素在根处
        T minItem = findMin();
        // 将最大的元素放置到根处，相当于删掉了根处的元素，同时使用抽象出来的方法下浮最大值。
        array[1] = array[currentSize];
        currentSize -= 1;
        // 将节点1处的值下浮
        percolateDown(1);
        return minItem;
    }

    public T findMin() {
        if (isEmpty()) {
            throw new RuntimeException();
        }
        return array[1];
    }

    public boolean isEmpty() {
        return currentSize == 0;
    }

    private void percolateDown(int hole) {
        int child;
        // 要下浮的元素的值
        T temp = array[hole];
        for (; hole * 2 <= currentSize; hole = child) {
            // 左儿子的下标
            child = hole * 2;
            // 如果左儿子不是最后一个元素，并且右儿子小于左儿子，
            if (child != currentSize && array[child + 1].compareTo(array[child]) < 0) {
                // 要移动的则是较小的右儿子
                child++;
            }
            if (array[child].compareTo(temp) < 0) {
                // 如果子节点的值比要下浮的值小，那么子节点向上移动（相当于下浮节点下浮）
                array[hole] = array[child];
            } else {
                // 否则终止
                break;
            }
        }
        // temp移动到空穴位置
        array[hole] = temp;
    }

    /**
     * 扩容
     */
    private void enlargeArray(int newSize) {
        T[] old = array;
        array = (T[]) new Comparable[newSize];
        for (int i = 0; i < old.length; i++) {
            array[i] = old[i];
        }
    }

    public static void main(String[] args) {
        int numItems = 10000;
        BinaryHeap<Integer> h = new BinaryHeap<>();
        int i = 37;

        for (i = 37; i != 0; i = (i + 37) % numItems) {
            h.insert(i);
        }
        for (i = 1; i < numItems; i++) {
            System.out.println(h.findMin());
            h.deleteMin();
        }
    }
}