堆排序（排序思想+排序流程+代码）

排序思想

1. 大顶堆/小顶堆的根节点一定是当前堆的最大/最小值
2. 完全二叉树可以转化为数组

完全二叉树的性质

1. 节点数据2+1 = 他的左孩子，节点数据2+2 = 他的右孩子，如果不满足完全二叉树的定义，则不具备此规律
2. 左孩子一定是奇数，右孩子一定是偶数

这样的计算规律有什么好处呢？好处是我们可以用数组代替完全二叉树！

这样一个二叉树，使用广度优先遍历的方式放入数组，知道数组元素的下标，即可算出它的父结点，兄弟结点，以及它的孩子

父节点的计算方式：
下标为偶数：是右孩子，-2再÷2即为父节点
下标为奇数：是左孩子，-1再÷2即为父节点

兄弟结点：
下标为偶数：-1
下标为奇数：+1

孩子结点：
右孩子：*2+2
左孩子：*2+1

排序流程

一，构建完全二叉树

定义

高度为k的二叉树，二叉树的前k-1高度的树是满二叉树，最后一层必须优先左边满，被称为完全二叉树

简而言之就是：

1. 除了叶子结点，其余层必须都是满的
2. 叶子节点不能存在被“跳过去的情况（只有右没有左）

只要数据是从上到下，从左到右依次构建，就一定是一棵完全二叉树

构建例子

比如这个数组

完全二叉树

二，构建大根堆/小根堆（最难）

以大顶堆为例子

1. 让parent游标从后向前移动，直到parent游标有孩子，然后让child游标指向孩子

定义一个parent游标，定义一个child游标
如果一个结点有子树，那么其一定有左子树
左子树的公式：2*parent+1

2. 若左右子树都有，则让child指向两者中较大的那个

3. parent游标和child游标指向的值比较大小，若parent小则交换

此时依然不是大顶堆

4. 一旦完成交换，parent指向child的位置，child指向新的parent的左右孩子中最大的，进行比较（本质上就是重复执行3，4步），直到parent大于child/或者child指向空（比如第一次交换，parent又指向了叶子节点，此时的child显然为null）

但是此时存在一个问题：难道parent从2重新遍历到6？其实不是，我们实现了一种机制，不需要再走循环，这里暂且不表，后续我们再说怎么实现这种机制

构建示意图

2比6小，交换

发生交换，父子指针也交换

运用某种机制，重新定位到7，6

向上遍历，最终定位到5，7，交换

发生交换，父子指针交换，56交换

再次发生交换，父子指针交换

构建完毕

堆顶堆底元素互换，重新构建大根堆，新的堆底元素不再参与

代码实现（注意看注释）

public static void main(String[] args) {
        int[] arr = {78, 76, 1, 55, 129, 45, 24};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void heapSort(int[] arr) {
        // 实际并没有构建完全二叉树，而是用不同的下标模拟了这个过程，所以堆排序才难写！！！
        for (int p = arr.length - 1; p >= 0; p--) {
            sort(arr, p, arr.length);
        }
        // 构建完成大顶堆，堆顶元素和堆底元素交换,重新构建大顶堆
        // 上面已经用过一次arr.length，所以这里从arr.length-1开始，i不能=0
        for (int i = arr.length - 1; i > 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            sort(arr, 0, i);
        }


    }

    public static void sort(int[] arr, int parent, int length) {// child为空
        // parent并没有自主向后移动的功能，否则parent不可能跳跃移动，一直是p带着parent移动！！！
        int maxChild = 2 * parent + 1;
        while (maxChild < length) {
            // 左孩子存在，则判断右孩子是否存在
            int rightChild = maxChild + 1;
            if (rightChild < length && arr[maxChild] < arr[rightChild]) {
                maxChild = rightChild;
            }
            // 父子结点值交换
            if (arr[maxChild] > arr[parent]) {
                int temp = arr[maxChild];
                arr[maxChild] = arr[parent];
                arr[parent] = temp;
                // 交换，则parent指向child指针,child指针指向新的parent的child,，
                parent = maxChild;
                maxChild = 2 * maxChild + 1;
            } else {
                // 不满足则跳出循环，防止死循环
                break;
            }
        }
    }

现在回答我们刚才提出的问题，指针是如何跳跃回去的呢？

因为parent不能主动移动，其实是根据p指针移动的，所以当parent指针运行完毕之后，p–，看上去好像是parent突然跳跃了一样