排序算法---堆排序（Java）

在完全二叉树中，结点i的左孩子为2i，右孩子为2i+1，双亲为i/2取整。
由于数组是从0开始，下标计算变为：
left = parent*2+1
right = parent*2+2
parent = (child-1)/2

public class HeapSortTest {
    public static void main(String[] args) {
        int[] arr = new int[]{2, 3, 1, 0, 5, 4, 7, 9, 8, 6};
        heapSort(arr, arr.length);
        Arrays.stream(arr).forEach(val -> System.out.print(val + " "));
    }

    private static void heapSort(int[] arr, int n) { //堆排序，n为待排序元素个数
        for (int i = (n - 2) / 2; i >= 0; i--) { //从最后一个结点的双亲开始构造堆
            heapAdjust(arr, i, n);
        }
        for (int i = n - 1; i > 0; i--) { //每次将堆顶元素放在末位，且不参与下一轮
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            heapAdjust(arr, 0, i);
        }
    }

    private static void heapAdjust(int[] arr, int p, int n) { //调整堆，p为本次要调整双亲结点下标
        int p_val = arr[p]; // 先暂存双亲结点值
        int i;
        for (i = 2*p+1; i < n; i = 2*i+1) { //i初始为左孩子
            if ((i + 1) < n && arr[i + 1] > arr[i]) i++; //如果右孩子大于左孩子，构造大顶堆则把此处改成<
            if (p_val >= arr[i]) break; //如果双亲大于等于两个孩子，不用继续往下了，构造大顶堆则把此处改成<=
            arr[p] = arr[i]; //将更大的那个孩子上移至双亲位置
            p = i; //双亲指针继续往下
        }
        arr[p] = p_val; //将双亲结点值放入正确位置
    }
}