堆排序的特点

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

堆排序具有以下特点：

①:完全二叉树(从上到下，从左到右，每一层的节点都是满的，最下边一层所有的节点都是连续集中在最左边)。

②:二叉树每个结点的值都大于或者等于其左右孩子节点的值称之为大顶堆。

二叉树每个结点的值都小于或者等于其左右孩子节点的值称之为小顶堆。

我们将数组转化为堆的数据结构

我们可以看到以下的规律

N[i]的左节点:N[2i+1]

N[i]的右节点:N[2i+2]

N[i]的父节点:N[(i-1)/2)]

基本思想

1):将带排序的序列构造成一个大顶堆，根据大顶堆的性质，当前堆的根节点（堆顶）就是序列中最大的元素

2):将堆顶元素和最后一个元素交换，然后将剩下的节点重新构造成一个大顶堆；

3):重复步骤2，如此反复，从第一次构建大顶堆开始，每一次构建，我们都能获得一个序列的最大值，然后把它放到大顶堆的尾部。最后，就得到一个有序的序列了

图示：

第一步：构建大顶堆

①:初始化状态，右下角为下标

②: index = 5开始，发现他没有兄弟节点，并且父节点小于它，父节点的计算放方式为：

index = [arr.length - 1] /2

③:接下来index减1，那么index节点变为4，这时候他要和兄弟节点进行对比，发现它比兄弟节和父节点都大

那么他就和父节点机型交换。

④:接下来index减2，他有和兄弟节点进行对比，发现它比兄弟节点大，还比父节点大，那么它和父节点进行交换

④:交换完成之后，发现2号节点不再大于其子节点了，所有需要在交换一次

//选取孩子结点的左孩子结点,继续向下筛选 parent = lChild; lChild = 2 * lChild + 1;

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

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

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

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

③:再次调整，index = 1 ，此时 下标为1的值为5，值大于左右子树，所以 index -1 ，此时值为1.然后需要进行交换

交换完成之后，发现1号节点不再大于其子节点了，所有需要在交换一次

④：交换后的结果是

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

⑥:此时的堆不是大顶堆需要重现构建,此时 index = 1,1号位置大于其孩子节点的值，所以 index -1 ，此时index = 0

0号位置小于其左子树。所以进行交换

⑦:交换后的结果是

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

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

⑩:交换后的结果是

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

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

十三:交换后的结果是

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

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

代码

public class HeapSort {
	  public static void main(String[] args) {
//        int[] arr = {5, 1, 7, 3, 1, 6, 9, 4};
        int[] arr = {16, 7, 3, 20, 17, 8};

        heapSort(arr);

        for (int i : arr) {
            System.out.print(i + " ");
        }
    }


    /**
     * 创建堆，
     * @param arr 待排序列
     */
    private static void heapSort(int[] arr) {
        //创建堆
        for (int i = (arr.length - 1) / 2; i >= 0; i--) {
            //从第一个非叶子结点从下至上，从右至左调整结构
            adjustHeap(arr, i, arr.length);
        }

        //调整堆结构+交换堆顶元素与末尾元素
        for (int i = arr.length - 1; i > 0; i--) {
            //将堆顶元素与末尾元素进行交换
            int temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;

            //重新对堆进行调整
            adjustHeap(arr, 0, i);
        }
    }

    /**
     * 调整堆
     * @param arr 待排序列
     * @param parent 父节点
     * @param length 待排序列尾元素索引
     */
    private static void adjustHeap(int[] arr, int parent, int length) {
        //将temp作为父节点
        int temp = arr[parent];
        //左孩子
        int lChild = 2 * parent + 1;

        while (lChild < length) {
            //右孩子
            int rChild = lChild + 1;
            // 如果有右孩子结点，并且右孩子结点的值大于左孩子结点，则选取右孩子结点
            if (rChild < length && arr[lChild] < arr[rChild]) {
                lChild++;
            }

            // 如果父结点的值已经大于孩子结点的值，则直接结束
            if (temp >= arr[lChild]) {
                break;
            }

            // 把孩子结点的值赋给父结点
            arr[parent] = arr[lChild];

            //选取孩子结点的左孩子结点,继续向下筛选
            parent = lChild;
            lChild = 2 * lChild + 1;
        }
        arr[parent] = temp;
    }

}