• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

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

开发技术 开发技术 14分钟前 2次浏览

目录
  • 基本介绍
    • 大顶堆举例
    • 小顶堆举例
    • 排序说明
  • 基本思想
  • 排序步骤图解
    • 步骤一:构造初始堆
    • 步骤二:将堆顶元素与末尾元素进行交换
    • 思路总结
  • 代码实现
    • 步骤推演
    • 完整实现
  • 性能测试

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

基本介绍

排序(英语: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 开始

排序说明

  • 升序:一般采用大顶堆
  • 降序:一般采用小顶堆

基本思想

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

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

    关于顺序存储二叉树请看 数据结构与算法——二叉树

  2. 此时:整个序列的 最大值就是堆顶的根节点

  3. 将其 与末尾元素进行交换,而后此时末尾就是最大值

  4. 然后将剩余 n-1 个元素重新构造成一个堆,这样 就会得到第 n 个元素的次小值。如此反复,便能的得到一个有序序列。

动图初体验:
数据结构与算法——堆排序

堆排序步骤图解

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

步骤一:构造初始堆

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

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

    下面将给定无序序列构造成一个大顶堆。

  2. 此时从最后一个非叶子节点开始调整从左到右,从上到下进行调整。

    叶节点不用调整,第一个非叶子节点 arr.length/2-1 = 5/2-1 = 1,也就是 元素为 6 的节点。

    比较时,先让 5 与 9 比较,得到最大的那个,再和 6 比较,发现 9 大于 6,则调整他们的位置。
    

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

  3. 找到第二个非叶子节点 4,由于 [4,9,8] 中,9 元素最大,则 4 和 9 进行交换

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

  4. 此时,交换导致了子根 [4,5,6] 结构混乱,将其继续调整。[4,5,6] 中 6 最大,将 4 与 6 进行调整。

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

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

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

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

  1. 将堆顶元素 9 和末尾元素 4 进行交换

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

  2. 重新调整结构,使其继续满足大顶堆定义,这里要把 9 除外,因为 9 已经是排好序的了

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

  3. 再将堆顶元素 8 与末尾元素 5 进行交换,得到第二大元素 8

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

  4. 后续过程,继续进行调整、交换,如此反复进行,最终使得整个序列有序

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

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

思路总结

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

代码实现

步骤推演

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

    @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
        // 到这里就构造成了一个大顶堆
    }

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

完整实现

这里想说的几点注意事项(代码实现的关键思路):

  1. 第一步构建初始堆:是自下向上,从左到右

    从下往上构建初始堆是为了:每一层的大顶堆一定比它的下一层左右两节点大,也就是说,每一层都比下一层大。但是,左右是不要求大小的

  2. 第二步让尾部元素与堆顶元素交换,最大值被放在数组末尾

  3. 第三步:是从上到下,从左到右

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

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

 @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 毫秒左右 。


程序员灯塔
转载请注明原文链接:数据结构与算法——堆排序
喜欢 (0)