数据结构与算法——堆排序

2021 年 9 月 12 日
筆記
数据结构与算法

基本介绍
基本思想
堆排序步骤图解
代码实现
- 步骤推演
- 完整实现
性能测试

注意：学习本篇需要学会二叉树关于二叉树的学习请看数据结构与算法——二叉树

基本介绍

堆排序（英语：Heapsort）是利用堆这种 数据结构 而设计的一种排序算法，堆是一个近似完全二叉树的结构，它是一种选择排序，最坏、最好、平均时间复杂度均为 O(nlogn)，它是不稳定排序。

堆是具有以下性质的完全二叉树：

大顶堆：每个节点的值都 大于或等于 其左右孩子节点的值

注：没有要求左右值的大小关系
小顶堆：每个节点的值都 小于或等于 其左右孩子节点的值

注：没有要求左右值的大小关系

举例说明：

大顶堆举例

对堆中的节点按层进行编号，映射到数组中如下图

大顶堆特点：arr[i] >= arr[2*i+1] && arr[i] >= arr[2*i+2]，i 对应第几个节点，i 从 0 开始编号

小顶堆举例

小顶堆特点：arr[i] <= arr[2*i+1] && arr[i] <= arr[2*i+2]，i 对应第几个节点，i 从 0 开始

排序说明

升序：一般采用大顶堆
降序：一般采用小顶堆

基本思想

将待排序序列构造成一个大顶堆

注意：这里使用的是数组，而不是一棵二叉树，用的是顺序存储二叉树

关于顺序存储二叉树请看数据结构与算法——二叉树
此时：整个序列的 最大值就是堆顶的根节点
将其 与末尾元素进行交换，而后此时末尾就是最大值
然后将剩余 n-1 个元素重新构造成一个堆，这样就会得到第 n 个元素的次小值。如此反复，便能的得到一个有序序列。

动图初体验：

堆排序步骤图解

对数组 4,6,8,5,9 进行堆排序，将数组升序排序。

步骤一：构造初始堆

给定无序序列结构如下：注意这里的操作用数组，树结构只是参考理解

下面将给定无序序列构造成一个大顶堆。
此时从最后一个非叶子节点开始调整，从左到右，从上到下进行调整。

叶节点不用调整，第一个非叶子节点 arr.length/2-1 = 5/2-1 = 1，也就是元素为 6 的节点。
```
比较时，先让 5 与 9 比较，得到最大的那个，再和 6 比较，发现 9 大于 6，则调整他们的位置。
```
找到第二个非叶子节点 4，由于 [4,9,8] 中，9 元素最大，则 4 和 9 进行交换
此时，交换导致了子根 [4,5,6] 结构混乱，将其继续调整。[4,5,6] 中 6 最大，将 4 与 6 进行调整。

此时，就将一个无序序列构造成了一个大顶堆。

步骤二：将堆顶元素与末尾元素进行交换

将堆顶元素与末尾元素进行交换，使其末尾元素最大。然后继续调整，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。

将堆顶元素 9 和末尾元素 4 进行交换
重新调整结构，使其继续满足大顶堆定义，这里要把 9 除外，因为 9 已经是排好序的了
再将堆顶元素 8 与末尾元素 5 进行交换，得到第二大元素 8
后续过程，继续进行调整、交换，如此反复进行，最终使得整个序列有序

如果还不懂，就结合上面的动图再看一遍。

思路总结

将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆
将堆顶元素与末尾元素交换，将最大元素「沉」到数组末端
重新调整结构，使其满足堆定义，然后继续交换数组第一个元素与末尾元素，反复执行调整、交换步骤，直到整个序列有序。

代码实现

步骤推演

此推演，对照的是：堆排序步骤图解中的第一步骤构造大顶堆，注意对照图解进行理解代码含义

    @Test
    public void processSortTest() {
        int arr[] = {4, 6, 8, 5, 9};
        processSort(arr);
    }

    private void processSort(int[] arr) {
        // 第一次：从最后一个非叶子节点开始调整，从左到右，从上到下进行调整。
        // 参与比较的元素是：6,5,9
        int i = 1;
        int temp = arr[i]; // 6
        //这里i表示三数堆顶的数
        int k = i * 2 + 1; // i 的左节点

        // 要将这三个数（堆），调整为一个大顶堆
        // 判断 i 的左节点是否小于右节点
        if (arr[k] < arr[k + 1]) {
            k++; // 如果右边的大，则将 k 变成最大的那一个
        }
        // 如果左右中最大的一个数，比 i 大。则调整它
        if (arr[k] > temp) {
            arr[i] = arr[k];
            arr[k] = temp;
        }
        System.out.println(Arrays.toString(arr)); // 4,9,8,5,6

        // 第二次调整：参与比较的元素是  4,9,5
        i = 0;
        temp = arr[i]; // 4
        k = i * 2 + 1;
        //如上一次
        if (arr[k] < arr[k + 1]) {
            k++; // 如果右边的大，则将 k 变成最大的那一个
        }
        // 9 比 4 大，交换的是 9 和 4
        if (arr[k] > temp) {
            arr[i] = arr[k];
            arr[k] = temp;
        }
        System.out.println(Arrays.toString(arr)); // 9，4,8,5,6

        // 上面调整导致了，第一次的堆：4,5,6 的混乱。这里要对他进行重新调整
        i = 1;
        temp = arr[i]; // 4
        k = i * 2 + 1;
        if (arr[k] < arr[k + 1]) {
            k++; // 如果右边的大，则将 k 变成最大的那一个
        }
        // 6 比 4 大，交换它
        if (arr[k] > temp) {
            arr[i] = arr[k];
            arr[k] = temp;
        }
        System.out.println(Arrays.toString(arr)); // 9，6,8,5,4
        // 到这里就构造成了一个大顶堆
    }

剩下的，是交换序列首尾元素，并继续这个流程。

完整实现

这里想说的几点注意事项（代码实现的关键思路）：

第一步构建初始堆：是自下向上，从左到右。

从下往上构建初始堆是为了：每一层的大顶堆一定比它的下一层左右两节点大，也就是说，每一层都比下一层大。但是，左右是不要求大小的
第二步让尾部元素与堆顶元素交换，最大值被放在数组末尾。
第三步：是从上到下，从左到右

因为第二步的原因，变化在堆顶，所以从堆顶开始调整；

在初始堆的基础上，一层一层往下调整，如果到了某一层而这层不需要调整的话，则退出当次的调整，也就是说已经构建好了一个新的大顶堆，因为初始堆的特点：每一层都比下一层大，可以直接退出。

 @Test
    public void sortTest() {
        int[] arr = {4, 6, 8, 5, 9};
        sort(arr);
        int[] arr2 = {99, 4, 6, 8, 5, 9, -1, -2, 100};
        sort(arr2);
    }

    private void sort(int[] arr) {
        // =====  1. 构造初始堆
        // 从第一个非叶子节点开始调整
        // 4,9,8,5,6
        //  adjustHeap(arr, arr.length / 2 - 1, arr.length);

        // 循环调整
        // 从第一个非叶子节点开始调整，自下向上
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            adjustHeap(arr, i, arr.length);
        }
        // 第一轮调整了 3 个堆后：结果为：9，6,8,5,4
       

        // 2. 将堆顶元素与末尾元素进行交换，然后再重新调整
        int temp = 0;
        for (int j = arr.length - 1; j > 0; j--) {
            temp = arr[j];  // j 是末尾元素
            arr[j] = arr[0];
            arr[0] = temp;
            // 这里是从第一个节点开始: 不是构建初始堆了，而是重构
            // 如果
            adjustHeap(arr, 0, j);//j是要调整的数组长度，每次减 1，这里需要注意了！！！
        }
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 调整堆
     * 
     * @param arr	 数组
     * @param i      非叶子节点，以此节点为基础，将它、它的左、右，调整为一个大顶堆
     * @param length 需要构建成大顶堆的数组大小，除了构建初始堆的时候length=数组大小，其他时候的每一次重构堆都会减小 1
     */
    private void adjustHeap(int[] arr, int i, int length) {
        // 难点是将当前的数组首尾互换之后，影响到了它后面节点堆大小混乱，如何继续对影响后的堆进行调整
        // 所以第一步构造初始堆中：是一个额外循环的 从低向上 调整的
        //    第三步数组首尾交换后的堆重构中：就是 从上到下调整的，这个很重要，一定要明白
        //结合上面sort（）方法进行理解
        
        //需要调整的三数堆的堆顶元素
        int temp = arr[i];
        // 从传入节点的左节点开始处理
        for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
            // 要将这三个数（堆），调整为一个大顶堆
            // k+1 < length : 当调整长度为 2 时，也就是数组的前两个元素，其实它没有第三个节点了，就不能走这个判定，通俗点说就是防止越界
            if (k + 1 < length && arr[k] < arr[k + 1]) {
                k++; // 如果右边的大，则将 k 变成最大的那一个
            }
            // 如果左右中最大的一个数，比 i 大。则调整它
            if (arr[k] > temp) {
                arr[i] = arr[k];
                i = k; // i 记录被调整后的索引。这里为什么这样做，看下面的这句arr[i] = temp;以及上面arr[i] = arr[k];代码想一下
            } else {
                break;
                // 由于初始堆，就已经是大顶堆了，每个子堆的顶，都是比他的左右两个大的
                // 当这里没有进行调整的话，那么就可以直接退出了
                // 如果上面进行了调整。那么在初始堆之后，每次都是从 0 节点开始 自左到右，自上而下调整的
                //    就会一层一层的往下进行调整
            }
        }
        arr[i] = temp;//这里很重要！！！！
    }

测试信息

[4, 5, 6, 8, 9]
[-2, -1, 4, 5, 6, 8, 9, 99, 100]

性能测试

    /**
     * 大量数据排序时间测试
     */
    @Test
    public void bulkDataSort() {
        int max = 800000;
//        int max = 8;
        int[] arr = new int[max];
        for (int i = 0; i < max; i++) {
            arr[i] = (int) (Math.random() * max);
        }
        if (arr.length < 10) {
            System.out.println("原始数组：" + Arrays.toString(arr));
        }
        Instant startTime = Instant.now();
        sort(arr);
        if (arr.length < 10) {
            System.out.println("排序后：" + Arrays.toString(arr));
        }
        Instant endTime = Instant.now();
        System.out.println("共耗时：" + Duration.between(startTime, endTime).toMillis() + " 毫秒");
    }

多次测试输出

共耗时：163 毫秒
共耗时：211 毫秒
共耗时：165 毫秒

可以看到他的速度非常快，在我的机器上，800 万数据 160 毫秒左右。

Tags: 数据结构与算法