堆排序

二叉堆的定义：二叉堆是一组能够用堆有序的完全二叉树排序的元素，并在数组中按照层级储存（不使用数组的第一个元素）。
堆有序：一课二叉树的每个节点都大于等于他的两个子节点
完全二叉树：除了最后一层外的其他每一层都 都被完全填充，最后一层向左对齐。

一图胜千言：

//这里的数组是从1开始排列的
    public void sort(Comparable[] a) {
        int n = a.length;
        for (int k = n / 2; k >= 1; k--) {
            sink(a, k, n);
        }
        while (n > 1) {
            exch(a, 1, n--);
            sink(a, 1, n);
        }
    }

    private void sink(Comparable[] a, int k, int n) {
        while (2 * k <= n) {
            int j = 2 * k;
            if (j < n && less(a, j, j + 1))
                j++;
            if (!less(a, k, j))
                break;
            exch(a, k, j);
            k = j;
        }
    }

    private boolean less(Comparable[] a, int i, int j) {
        return a[i - 1].compareTo(a[j - 1]) < 0;
    }

    private void exch(Object[] a, int i, int j) {
        Object temp = a[i - 1];
        a[i - 1] = a[j - 1];
        a[j - 1] = temp;
    }

方法解读在优先队列