专栏首页编程珠玑图解:基于二叉堆的堆排序是如何实现的?

图解:基于二叉堆的堆排序是如何实现的?

前言

我们在介绍《什么是优先队列》的时候就注意到,如果每次都删除堆顶元素,那么将会得到一个有序的数据。因此,我们可以利用二叉堆来对数据进行排序。

堆排序分析

通过前面的学习我们可以看到,如果构建一个二叉堆,最后每次从堆顶取出一个元素,那么最终取出元素就是有序的,不过如果要用来对数据按照从小到大排序,就不是构造小顶堆,而是大顶堆了,即堆顶元素大于等于其左右儿子节点。总结堆排序思路如下:

  • 以O(N)时间复杂度构建N个元素的二叉堆
  • 以O(logN)时间复杂度删除一个堆顶元素,N个元素时间复杂度为O(NlogN)
  • 由于删除一个堆顶元素时,就会空出一个位置,为了节省空间,将删除的堆顶元素放到数组末尾
  • 当堆为空时,完成排序
  • 由于数组元素从下标0开始,因此每个位置必须利用好。假设堆顶元素位置为i,那么左右儿子节点位置分别为2i+1,2i+2

实例分析

根据前面的分析,我们来看一个具体的例子。假设我们要对

1 10 8 5 7 15 35

进行排序。

该数据构成的原始二叉树如下:

二叉树

构建二叉堆

为了能够使得数组所有元素满足堆的性质,即父节点大于等于儿子节点,我们需要从倒数第二层开始调整(为什么不是从最后一层?)。即调整8和10。 对于8来说,找到它的儿子节点中较大的一个,即35,将8和35交换后如下:

第一次交换后

此时数组数据为:

1 10 35 5 7 15 8 

对于10来说,它比左右儿子节点都大,因此不需要调整。

对于1来说,它的右儿子35最大,因此需要调整,和右儿子交换后如下:

第二次交换后

此时数组数据为:

35 10 1 5 7 15 8 

但是一次交换后,我们发现,1的左儿子还是比它大,因此交换它和较大的左儿子的位置,交换后如下:

第三次交换后

此时数组数据为:

35 10 15 5 7 1 8

最终我们得到了满足堆性质的二叉堆了。

基于二叉堆的排序

在堆创建好后,每次取出堆顶元素,并且调整堆,把堆顶元素放在数组最后即可。 例如,对于前面创建好的堆,堆顶元素是35,我们取出第i(此时为1)个元素35,并把堆最后一个元素放在数组倒数第i个位置:堆顶元素交换

为了满足堆性质,我们需要调整堆顶元素,因为堆顶元素目前不满足堆性质,因此需要交换8和15的位置:

调整位置

此时所有元素再次满足堆性质。

此时数组数据为:

15 10 8 5 7 1 35

对于其他元素也是同样的操作,因此不再赘述。

代码实现

根据上面的分析,关键代码实现如下:

void adjust_ele(ElementType arr[],int i,int length)
{
    int child ;
    ElementType temp;
    for(temp = arr[i];2*i+1 < length;i = child)
    {
        child = 2 * i +1;

        /*找到较大的儿子*/
        if(child != length-1 && arr[child+1] > arr[child])
            child+=1;
        /*如果空穴元素小于该儿子,则空穴下滑*/
        if(temp < arr[child])
           arr[i] = arr[child];
        else
         break;
    }
    /*将i位置的元素放到正确的位置*/
    arr[i] = temp;
}
void heap_sort(ElementType arr[],int length)
{
    int i = 0;
    /*构建堆*/
    for(i = length /2;i >= 0;i--)
    {
        adjust_ele(arr,i,length);
        //printArr(arr,length);
    }
    for(i = length-1;i > 0;i--)
    {
        /*填充i位置的空穴*/
        swap(&arr[0],&arr[i]);

        /*每次都处理堆顶元素*/
        adjust_ele(arr,0,i);
        //printArr(arr,length);
    }
}

完整可运行代码地址可点击阅读原文或访问:https://www.yanbinghu.com/2019/06/04/26564.html

运行结果:

before sort:1 10 8 5 7 15 35 
after  sort:1 5 7 8 10 15 35

总结

结合我们前面介绍的优先队列,我们很容易理解堆排序,不过需要注意的就是位置0必须使用上。另外通过利用删除堆顶元素后空出来的位置,避免了另外申请数组内存来存放排序好的数组。建议自己修改完整可运行代码,来观察数据调整情况。

本文分享自微信公众号 - 编程珠玑(shouwangxiansheng),作者:守望先生

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-06-05

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Linux下如何拆分大的日志文件?

    没设置好日志大小最大值,导致日志文件过大,普通编辑器根本没法打开或者特别卡,怎么办?拆分呗。

    编程珠玑
  • 一个超轻量级的JSON解析器

    众所周知,JSON是一种轻量级的数据格式,应用广泛。在C/C++应用中也常常作为配置文件或者数据的存储,因此JSON文件的生成和解析是必备知识。

    编程珠玑
  • 如何理解 Linux shell中“2>&1”?

    这里的2>&1是什么意思?该如何理解? 先说结论:上面的调用表明将./test.sh的输出重定向到log.txt文件中,同时将标准错误也重定向到log.txt文...

    编程珠玑
  • 一个简洁、有趣的无限下拉方案

    长列表渲染、无限下拉也算是前端开发老生常谈的问题之一了,本文将介绍一种简洁、巧妙、高效的方式来实现。话不多说,看下图,也许你可以发现什么

    Nealyang
  • 没人看系列----css 随笔

    kmonkey
  • 计算机理论基础知识-Internet应用

    刘金玉编程
  • 腾讯“互联网+”指数·辽宁篇(2015年第一期)

    ? 1.腾讯“互联网+”指数及其代表意义   在宏观经济领域,为了能客观、快速地了解经济运行及发展趋势,我们往往会采用一些指标、指数对经济现状进行描述。这些指...

    腾讯研究院
  • scrapy常用配置

    SPIDER_MODULES = ['Amazon.spiders'] NEWSPIDER_MODULE = 'Amazon.spiders'

    小小咸鱼YwY
  • [论文品读]·d-vector解读(Deep Neural Networks for Small Footprint Text-Dependent Speaker Verification)

    在本文中,我们研究深度神经网络(DNNs)在小型文本相关的说话者验证任务的应用。在开发阶段,DNN经过训练,可以在帧级别对说话人进行分类。在说话人录入阶段,使用...

    小宋是呢
  • 腾讯刘琼:“互联网+”助力服装行业新发展

    9月21日,2015中国(大连)国际服装纺织品博览会期间,互联网+服装纺织行业的新机遇高峰论坛在大连举行。腾讯研究院高级研究员刘琼受邀发表演讲。出席论坛的还有...

    腾讯研究院

扫码关注云+社区

领取腾讯云代金券