/** * 时间复杂度O(NLogN), 空间复杂度O(1) * @author Wu * */public class HeapSort {        private static int[] arr = new int[]{1,0};    public static void main(String[] args) {        // 堆排        heapSort(arr);        // 打印排序后的数组        print(arr);    }        private static void heapSort(int[] arr) {                // 将待排序的序列构建成最大堆,从最后一个父节点开始        for(int i = arr.length / 2 - 1; i >= 0; i--) {            buildMaxHeapify(arr, i, arr.length);        }                // 逐步将每个最大值的根节点与末尾元素交换，并且再调整二叉树，使其成为大顶堆         for(int i = arr.length - 1; i >= 0; i--) {                        // 将堆顶记录和当前未经排序子序列的最后一个记录交换              int tmp = arr[0];              arr[0] = arr[i];              arr[i] = tmp;                       buildMaxHeapify(arr, 0, i); // 交换之后，需要重新检查堆是否符合大顶堆，不符合则要调整          }                            }    /**     * 构建最大堆过程     * @param arr    原数组     * @param i    根节点序号     * @param length    数组长度     */    private static void buildMaxHeapify(int[] arr, int i, int length) {        int largerChild;        int top = arr[i];        while(i < length / 2) {            // 只要i不在堆的最底层，也就是它只要至少还有一个子节点，就一直循环            int leftChild = 2 * i + 1;            int rightChild = 2 * i + 2;                        // 找最大的子节（要考虑右子节点不存在的情况）            if(rightChild < length && arr[rightChild] > arr[leftChild]) {                largerChild = rightChild;            } else {                largerChild = leftChild;            }                        // 交换根节点与子节点，使满足最大堆                        if(top >= arr[largerChild]) {                break;            }                        arr[i] = arr[largerChild];            i = largerChild;        }        arr[i] = top;      }            private static void print(int[] arr) {        for(int i = 0; i < arr.length; i++) {            System.out.print(arr[i] + " ");        }            }            }