一、完全二叉树

完全二叉树是一种特殊的二叉树。从上大下，从左到右，每一层的结点都是满的，最下边一层所有的节点都是连续集中在最左边。

二、堆

堆排序分为两种，分别是大顶堆和小顶堆

1. 大顶堆：在完全二叉树的基础上，每个节点的值都大于或等于其左右孩子节点
2. 小顶堆：在完全二叉树的基础上，每个节点的值都小于或等于其左右孩子节点的值

三、堆排序的特点

堆排序是利用堆这种数据结构而设立的一种排序算法

构建完全二叉树

基本思想

1. 将待排序的序列构造成一个大顶堆，根据大顶堆的性质，当前堆的根节点就是序列中的最大的元素
2. 将堆顶元素和最后一个元素交换，然后剩下的节点重新构造成一个大顶堆；
3. 重复步骤2，如此反复，从第一次构建大顶堆开始，每一次构建，我们都能获得一个序列的最大值，然后把它放到大顶堆的尾部。最后，就得到一个有序的序列了

图示

第一步：构建大顶堆(这里我们都是以最后一个开始讲解，不在是中间位置，讲解游标i的时候需要带上i的下边是一个大顶堆)

1. :初始化状态，右下角为下标
   
2. : index = 5开始，发现它没有兄弟节点，并且父节点小于它，父节点的计算放方式为：
   index = [arr.length - 1] /2
   
3. :接下来index减1，那么index节点变为4，这时候他要和兄弟节点进行对比，发现它比兄弟节和父节点都大
   那么他就和父节点机型交换。
   
4. :接下来index减2，他有和兄弟节点进行对比，发现它比兄弟节点大，还比父节点大，那么它和父节点进行交换
   
5. :交换完成之后，发现2号节点不再大于其子节点了，所有需要在交换一次
   //选取孩子结点的左孩子结点,继续向下筛选
   parent = lChild;
   lChild = 2 * lChild + 1;

6. :检查一下，已将满足最大的条件了，大顶堆已经构建完成
   

第二步：将堆顶元素和最后一个元素交换，然后将剩下的节点重新构造成一个大顶堆

1. :0号节点是最大值，我们将它与最后一个节点交换位置
   

2. :此时的堆不是大顶堆需要重现构建
   

3. :再次调整，index = 1 ，此时 下标为1的值为5，值大于左右子树，所以 index -1 ，此时值为1.然后需要进行交换
   交换完成之后，发现1号节点不再大于其子节点了，所有需要在交换一次
   

4. ：交换后的结果是
   

5. :0号节点是最大值，我们将它与最后一个节点交换位置
   

6. :此时的堆不是大顶堆需要重现构建,此时 index = 1,1号位置大于其孩子节点的值，所以 index -1 ，此时index = 0
   0号位置小于其左子树。所以进行交换
   

7. :交换后的结果是
   

8. ：0号节点是最大值，我们将它与最后一个节点交换位置
   

9. :此时的堆不是大顶堆需要重现构建,此时 index = 0,0号位置小于其孩子节点的值，左右子树进行计较之后发现右子树更大，所以和右子树进行交换。
   

10. :交换后的结果是
    

11. ;0号节点是最大值，我们将它与最后一个节点交换位置
    

12. ：此时的堆不是大顶堆需要重现构建,此时 index = 0,0号位置小于其孩子节点的值，左右子树进行计较之后发现做子树更大，所以和右子树进行交换。
    

13. :交换后的结果是
    

14. ;0号节点是最大值，我们将它与最后一个节点交换位置
    

最终我们就能得到最后的答案

代码

public class HeapSort {
    

    public static void main(String[] args) {
    
        int[] arr = new int[]{
    587,956,12,47,30,20,15,11,21,31,57,91,35,120};
        for (int p = arr.length-1;p>=0;p--){
    
            sort(arr,p,arr.length);
        }
        for(int i = arr.length-1; i>0;i--){
    
            int temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;

            sort(arr,0,i);
        }
        System.out.println(Arrays.toString(arr));
    }

    /** * 构建大顶堆的逻辑 * @param arr * @param parent * @param length */
    public static void sort(int[] arr,int parent,int length){
    
        int Child = 2 * parent +1; //左孩子
        while(Child < length){
    
            // 判断有没有右孩子，以及右和左孩子谁大
            int rChild = Child+1;
            if(rChild < length && arr[rChild] > arr[Child]){
    
                Child ++;
            }
            // 父子节点进行对比
            if(arr[parent] < arr[Child]){
    
                int temp = arr[parent] ;
                arr[parent]= arr[Child];
                arr[Child] = temp;

                parent = Child;
                Child = 2 * Child +1;
            }else{
    
                break;
            }
        }
    }

}