算法：通过堆排序，获取前N个最大数

在一组无序数组中，比如｛1，9，8，2，7，3，6，4，5｝

将数组看做是一个堆，也可以用二叉树来表示

但是这个堆现在还不是大顶堆，大顶堆的特点是父节点永远大于左右子节点

第一步需要将这个堆构建成大顶堆

构建前需要知道的几点：

二叉树的最后一个非叶子节点，计算公式是：array.length / 2 - 1

非叶子节点都是相邻的，这就是为什么buildMaxHeap方法中的i的步进方式是减1

父节点的左子节点的计算公式是：2 * i + 1

父节点的右子节点的计算公式是：2 * i + 2

buildMaxHeap方法的length参数意义：因为构建大顶堆后，根节点就成了最大值，此时将根节点和数组尾元素交换，就能将最大值移动到数组末尾，那么第一大的值已经确定，现在需要确定第二大的值，那么就需要在剩下的元素当中再次构建大顶堆，所以就需要控制后续构建大顶堆时的数组长度，也就是length

/*** 构建大顶堆** @param array  原始数组* @param length 需要构建的长度*/private static void buildMaxHeap(int[] array, int length) {    //从最后一个非叶子节点开始    for (int i = length / 2 - 1; i >= 0; i--) {        adjustHeap(array, i, length);    }}/*** 调整大顶堆** @param array  被调整数组* @param i      非叶子节点* @param length 需要调整的长度*/private static void adjustHeap(int[] array, int i, int length) {    //获取当前非叶子节点的值    int temp = array[i];    //依次遍历非叶子节点的左子节点    for (int j = 2 * i + 1; j < length; j = 2 * j + 1) {        //让j指向左右子节点较大的哪个        if (j + 1 < length && array[j] < array[j + 1]) {            j++;        }        //如果子节点>父节点        if (array[j] > temp) {            //让当前非叶子节点的值等于子节点的值            array[i] = array[j];            //让当前非叶子节点的下标指向当前字节点的下标            i = j;        } else {            //因为大顶堆是从下到上构建的，所以如果父节点是最大的那个的话就可以直接退出循环            break;        }        //让大的子节点等于之前非叶子节点的值        array[j] = temp;    }}

当无序数组第一次执行完buildMaxHeap方法后，已经可以确定根节点就是最大值，然后将根节点的值与元素末尾的值交换

然后循环这个过程

/*** 获取前n个最大的数** @param array 原始数组* @param n     前n个*/public static int[] heapSort(int[] array, int n) {    int size = n;    //第一次构建大顶堆    int length = array.length;    buildMaxHeap(array, length);    //此时顶端是数组中最大的节点，将顶端与数组末尾交换，然后在剩下的数组中再次构建大顶堆    while (n > 0 && n <= length) {        // 交换首尾元素        int temp = array[0];        array[0] = array[length - 1];        array[length - 1] = temp;        n--;        length--;        buildMaxHeap(array, length);    }    int[] result = new int[size];    System.arraycopy(array, array.length - size, result, 0, size);    return result;}

重点看这个地方

while (n > 0 && n <= length) {        // 交换首尾元素        int temp = array[0];        array[0] = array[length - 1];        array[length - 1] = temp;        n--;        length--;        buildMaxHeap(array, length);    }