首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >堆排序原来如此之简单

堆排序原来如此之简单

作者头像
蜻蜓队长
发布2019-03-18 15:35:24
4830
发布2019-03-18 15:35:24
举报
文章被收录于专栏:Android机动车Android机动车

堆排序(Heap Sort)是指利用堆这种数据结构所设计的一种排序算法。

我们知道,堆分为"最大堆"和"最小堆"。最大堆通常被用来进行"升序"排序,而最小堆通常被用来进行"降序"排序。 鉴于最大堆和最小堆是对称关系,理解其中一种即可。本文将对最大堆实现的升序排序进行详细说明。

堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆;或者每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆。如下图:

同时,我们对堆中的结点按层进行编号,将这种逻辑结构映射到数组中就是下面这个样子

该数组从逻辑上讲就是一个堆结构,我们用简单的公式来描述一下堆的定义就是:

大顶堆:arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]

小顶堆:arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

我们可以归纳出堆排序的基本步骤:

  • 把无序数组构建成二叉堆。
  • 循环删除堆顶元素,移到集合尾部,调节堆产生新的堆顶。

特别注意:堆与数组对应关系如下图:

根据堆与数组的对应关系,堆顶元素永远位于数组第一个位置,所以循环遍历时采用从后往前循环。

具体实现看代码(代码注释已经解释很清楚):

先构建大顶堆

    public void downAdjust(int[] array, int parentIndex, int length) {
        int temp = array[parentIndex];
        int childIndex = parentIndex * 2 + 1;
        while (childIndex < length) {
            // 如果有右孩子,两孩子中找到最大值
            if (childIndex + 1 < length && array[childIndex + 1] > array[childIndex]) {
                childIndex++;
            }
            // 如果父节点大于任一子节点值,则跳出
            if (temp >= array[childIndex]) {
                break;
            }
            // 子节点上浮,更新父节点和子节点索引
            array[parentIndex] = array[childIndex];
            parentIndex = childIndex;
            childIndex = 2 * parentIndex + 1;
        }
        // 完成替换
        array[parentIndex] = temp;
    }

循环删除堆顶元素,移到集合尾部,调节堆产生新的堆顶

    public void heapSort(int[] array) {
        // 1、无序数组构建为大顶堆
        for (int i = array.length - 1; i >= 0; i--) {
            downAdjust(array, i, array.length);
        }

        // 堆顶元素(第一个元素),移至数组末尾,继续对前部分构建大顶堆  循环
        for (int i = array.length - 1; i > 0; i--) {
            int temp = array[0];
            array[0] = array[i];
            array[i] = temp;

            downAdjust(array, 0, i);
        }
    }
本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2019-03-12,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 Android机动车 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 先构建大顶堆
  • 循环删除堆顶元素,移到集合尾部,调节堆产生新的堆顶
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档