堆排序

漫画：什么是二叉堆？
二叉堆：本质上是一种完全二叉树，又分为最大堆与最小堆。
最大堆：任何一个父节点的值，都大于等于它左、右孩子节点的值。最小堆可类比。
堆会根据这一特性进行自我调整，而我们的堆排序也是就此而来。

删除元素：删除堆顶的节点，然后把最后一个节点放到堆顶的位置，开始自我调整
增加元素：插入位置为二叉堆的最后一个位置，开始自我调整。
维持二叉堆的特性（以最大堆举例）：从最后一个非叶子节点开始下沉（也就是倒数第二排的最后一个非叶子节点），与孩子节点中比他小且较大的那个交换，（就是如果两个孩子都比他的父节点小，那么取较大的那个进行交换）

漫画：什么是堆排序？
注意：此时的二叉堆虽然能构成最大堆，但是仍然是相对无序的，我们仍然需要不断的删除堆顶元素来做到让其符合自然排序的规律。如下图所示：
需要明确的是：如果需要做到升序排序，那么我们需要最大堆来进行排序，且一次堆的调整只能获得一个堆顶的元素（第一次排序后获得的就是最大的数，第二次就是第二大的。。直到堆调整到其节点数-1次）。

来看下代码吧

public class heapSort {
    
    //这个是大顶堆的调整，升序排序需要大顶堆
    public static void downAdjust(int array[],int parentIndex,int length) {
        int childIndex=parentIndex*2+1;
        int temp=array[parentIndex];
        //当有孩子节点时
        while(childIndex<length) {
            //如果有右孩子，而且右孩子大于左孩子，那么就定位到右孩子
            if(childIndex+1<length&&array[childIndex]<array[childIndex+1]) {
                childIndex++;
            }
            //开始比较，如果父节点大于任意一个孩子节点，直接退出
            if(temp>=array[childIndex]) {
                break;
            }
            //开始下沉
            array[parentIndex]=array[childIndex];
            parentIndex=childIndex;
            childIndex=childIndex*2+1;
        
        }
        //父节点与孩子节点连续交换的时候（就是上面的三行代码），并不需要真的交换，只需要单项覆盖，循环结束后再把temp的值放到最终位置即可。
        array[parentIndex]=temp;
        
    }
    
    
    public static void  heapSort(int array[]) {
        //这边是构建初始的最大堆，i是parentIndex，array.length是长度。
        for(int i=(array.length-2)/2;i>=0;i--) {
            downAdjust(array,i,array.length);
        }
        //这边就是不断把堆顶元素放到数组最后，注意，此时第一次的downAdjust就已经把数组最后一位排除掉了。
        for(int i=array.length-1;i>0;i--) {
            int temp=array[i];
            array[i]=array[0];
            array[0]=temp;
            downAdjust(array,0,i);
        }
    }

   public static void main(String[] args) {
       int [] array =new int [] {7,1,3,10,5,2,8,9,6};
       heapSort(array);
       System.out.println(Arrays.toString(array));
    
}
}