✨堆结构✨

  堆就是一颗完全二叉树，堆结构要指明大根堆还是小根堆。我们用数组表示的完全二叉树，使用heapSize控制堆的大小，也就是数组中的前heapSize个数代表这个完全二叉树。

❤️大根堆👇

  每棵子树都满足头节点是最大的，或者说每个节点的值都大于或等于它的子节点的值。来个例子：

image.png

🤔上移：heapInsert

//当前位置的值 和自己的父亲比较，谁大，谁往上跑
private void heapInsert(int[] arr,int index){
    while(arr[index] > arr[(index-1)/2]{
        swap(arr,index,(index-1)/2);
        index = (index-1)/2;
    }
}

image.png

🤔下沉：heapify

    // 从index位置，往下看，不断的下沉
    private void heapify(int[] arr, int index, int heapSize) {
        int left = index * 2 + 1;
        // 停：较大的孩子都不再比index位置的数大；已经没孩子了
        while (left < heapSize) { // 如果有左孩子，有没有右孩子，可能有可能没有！
            // 把较大孩子的下标，给largest
            int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
            // 孩子和当前值比，谁大，就留谁
            largest = arr[largest] > arr[index] ? largest : index;
            //最大的就是自己，结束
            if (largest == index) {
                break;
            }
            // index和较大孩子，要互换
            swap(arr, largest, index);
            //继续循环
            index = largest;
            left = index * 2 + 1;
        }
    }

🤔相关使用

  排序就是因为数据无序，假设我们原本有个大根堆，里面有些数据错误了，那怎么调整这个数据才重新变成大根堆呢？就是调用上面的“上移”和“下沉”。解释一下：

  当数据发生变化的时候，有两种情况，

1. 数据变大了

   1. 本来我就是大根堆，数据从上往下是依次变小的，我这个数据变大了，肯定比下面的大
   2. 所以我不需要下沉了，我上移就可以了，调用一次heapInsert

2. 数据变小了

   1. 本来我是大根堆，数据从上往下依次变小，我这个数据变小了，仍然比上面的小
   2. 所以我不需要上移了，我直接下沉，调用一次heapify

还有一种情况是，我不知道这个数据是变大还是变小，我只知道它变了，那我就调一次heapInsert，再调一次heapify。

❤️小根堆

  每棵子树都满足头节点是最小的，或者说每个节点的值都小于或等于它的子节点的值。来个例子：

image.png

小根堆也有“上移”“下沉”，和大根堆的区别只是，谁小谁上移，谁大谁下沉。

✨复杂度

  堆的基本操作就是“上移”，“下沉”，这些操作只和自己的父亲或孩子比较，也就是每次比较都是相邻的两层。那么堆这个完全二叉树的高度，就决定了比较的最大次数，所以复杂度就是O(logN)的。

✨堆排序

  简单梳理一下逻辑，可以肯定是大根堆的头，一定是整个大根堆最大的值，那么我只需要将这个大根堆的头，给换到数组的最后，然后减少大根堆大小，循环操作，这样就将数组从最后位置往前依次排好序了吧。

1. 先把整个数组转成大根堆
2. 这个时候heapSize就是数组的大小N，0位置的数就是大根堆的头节点最大的，那么0和N-1位置的数交换，就将最大数，换到最后面了，然后将heapSize-1，将这最后这个数从大根堆踢出去。
3. 然后0到N-1，因为0位置数据改变了，所以要保证它继续是大根堆，需要进行调整
4. 对0位置进行heapify，下沉操作，让它重新变成大根堆。
5. 这个时候0位置又变成大根堆的头节点了，0再继续和大根堆的最后一个值交换（N-2），然后heapSize再-1。
6. 循环执行逻辑，heapSize为0结束。

❤️代码实现

    public static void heapSort2(int[] arr) {
        // 考虑边界
        if (arr == null || arr.length < 2) {
            return;
        }
        // 使用下沉操作，将数组换成大根堆
        for (int i = arr.length - 1; i >= 0; i--) {
            heapify(arr, i, arr.length);
        }
        // 初次的heapSize
        int heapSize = arr.length;
        // 将0位置的数和最后的数交换，然后heapSize减一
        swap(arr, 0, --heapSize);
        // heapSize有值就继续，没有值说明交换完了
        while (heapSize > 0) {
            // 0位置数据产生变化了，而且是往小变化，所以下沉操作，重新变成大根堆
            heapify(arr, 0, heapSize);
            // 变成大根堆了，0位置又变成最大值了，再和最后一个数交换，然后heapSize减一
            swap(arr, 0, --heapSize);
        }
    }