堆排序

完全二叉树

完全二叉树：树深为k层，则除k层外，k-1层的节点全满，且第k层的节点向左靠拢 称为完全二叉树

堆

一种数据结构，分为最小根堆和最大的根堆。
最大根堆：根节点分别大于等于左右节点，且根节点为最大。
最小根堆：根节点分布小于等于左右节点，且根节点最小。

image.png
对应到一个数组里面应该有 大根堆：a[i] >= a[2i+1] && a[i] >=[2i+2]，小根堆：a[i] <= a[2i+1] && a[i] <=[2i+2]。

算法实现

1、首先我们将一个非有序的数据结构，长度为length调整为一个最大根堆，此时根节点为当前数组的最大值。
2、将最大值和末尾值交换，此时末尾为最大值，然后对前length -1个数据再次进行调整，完成之后根节点为次大值。
3、重复2步骤一直到根节点。此时已经完成了排序。且为升序排序。

      public void heapSort(int[]nums){
        //根据原有序列构建一个最大根堆
        //a[i] >=a[2i+1]
        //a[i] >= a[2i+1]
        //第一个叶子节点 一定是 nums.length /2 从后往前第一个非叶子节点一定是length.2-1
        int length = nums.length;
        //创建一个最大根堆
        for (int i = length/2-1; i>=0;i--){
            adjustHeap(nums,i,length);
        }
        //开始交换根节点和末尾节点 ，然后调整堆，使其
        for (int i = length-1; i >=0;i--){
            //交换根节点和最后一个节点，然后调整堆。
            int temp = nums[0];
            nums[0] = nums[i];
            nums[i] = temp;
            adjustHeap(nums,0,i);
        }
    }

  /**
     * 调整制定节点的堆
     * @param nums
     * @param i
     * @param length
     */
    public void adjustHeap(int[] nums,int i,int length){
        int temp = nums[i];
        for (int k = 2*i+1; k < length; k = k*2+1){
            if (k+1 < length && nums[k]<nums[k+1]){
                k++;
            }
            //子节点大于根节点 交换
            if (nums[k] >  temp){
                nums[i] = nums[k] ;
                i = k;
            }
        }
        nums[i] = temp; //调整到最佳位置
    }