堆排序总结

1. 默认将arr数组按照广度优先遍历的方式形成一个二叉树，该树满足以下特性：

• 如果含有子节点leftChildIndex的父节点的序号为parentIndex，arr总长度为len，则
• 对于任意parentIndex，均满足 parentIndex <= (len-1)/2，即叶子节点最多有 len - (len-1)/2
• leftChildIndex = 2*parentIndex + 1， 这是由每一层x的结点数都是 Math.pow(2, x)决定的

2. 从父节点最大的序号开始依次遍历各个子树，使得每个子树都是大根堆结构，需要先从子节点中找到最大的值，然后和父节点比对，如果交换了数据，还需要向下调整大根堆结构
3. 每次将大根堆的头结点的数据和最后一个叶子结点交换，交换后剪掉该叶子结点，并从头结点调整大根堆结构，循环直到大根堆只有一个结点为止。

package com.example.demo;

public class HeapSort {

    public static void main(String[] args) {
        int[] arr = {10,2,3,6,7,4,5,7,8,9};

        heapSort(arr);

        for (int i : arr) {
            System.out.print(i + " ");
        }
    }

    private static void heapSort(int[] arr) {
        int len = arr.length;
        //(arr.length-1)/2的index是第一个有子结点的父结点
        for(int i=(len-1)/2; i>=0;i--) {
            adjustHeap(arr, i, len);
        }
        for(int i = len-1;i>0;i--) {
            int temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;
            adjustHeap(arr, 0, i);
        }
    }

    /**
     *
     * @param arr 将arr调成成为 adjustLength 内的、子树的头结点序号是parentIndex的大根堆，
     * @param parentIndex 需要调整arr的范围，超过这个范围说明已经排序好了
     * @param adjustLength 子树的头结点序号是parentIndex，调整后该子树为大根堆
     */
    private static void adjustHeap(int[] arr, int parentIndex, int adjustLength) {
        int selectedIndex = parentIndex*2+1;
        int needAdjustNum = arr[parentIndex];
        while(selectedIndex < adjustLength) {
            int rightChildIndex = selectedIndex+1;
            if(rightChildIndex<adjustLength && arr[rightChildIndex] > arr[selectedIndex]) {
                selectedIndex = rightChildIndex;
            }
            if(needAdjustNum >= arr[selectedIndex]) {
                break;
            } else {
                arr[parentIndex] = arr[selectedIndex];
                parentIndex = selectedIndex;
                selectedIndex = parentIndex*2+1;
            }
        }
        arr[parentIndex] = needAdjustNum;
    }
}