图解：基于二叉堆的堆排序是如何实现的？

Bertha 。 2022-01-22 05:37 218阅读 0赞

来源：公众号【编程珠玑】

作者：守望先生

## 前言 ##

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

## 堆排序分析 ##

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

## 实例分析 ##

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

1 10 8 5 7 15 35

进行排序。

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

![640?wx\_fmt=png][640_wx_fmt_png]

二叉树

构建二叉堆

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

![640?wx\_fmt=png][640_wx_fmt_png 1]

第一次交换后

此时数组数据为：

1 10 35 5 7 15 8

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

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

![640?wx\_fmt=png][640_wx_fmt_png 2]

第二次交换后

此时数组数据为：

35 10 1 5 7 15 8

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

![640?wx\_fmt=png][640_wx_fmt_png 3]

第三次交换后

此时数组数据为：

35 10 15 5 7 1 8

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

基于二叉堆的排序

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

![640?wx\_fmt=png][640_wx_fmt_png 4]

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

![640?wx\_fmt=png][640_wx_fmt_png 5]

调整位置

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

此时数组数据为：

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 35sort:1 10 8 5 7 15 35 
    after  sort:1 5 7 8 10 15 35

## 总结 ##

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

推荐阅读：

[什么是优先队列？][Link 1]

[什么是二叉查找树？][Link 2]

[动画：二叉树遍历的多种姿势][Link 3]

关注公众号【编程珠玑】，获取更多Linux/C/C++/Python/Go/算法/工具等原创技术文章。后台免费获取经典电子书和视频资源

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

、、

[Link 1]: http://mp.weixin.qq.com/s?__biz=MzI2OTA3NTk3Ng==&mid=2649284710&idx=1&sn=9a85d3d1a3654dd19ab1fc07be196f4f&chksm=f2f99301c58e1a17b7c0953793039a788c505d9968f6f6a9f3fdac09fdd9a03af0ede1d1a1a5&scene=21#wechat_redirect
[640_wx_fmt_png]: /images/20220122/5ebf0f3dbb1a4392b99d6247762d76e9.png
[640_wx_fmt_png 1]: /images/20220122/6f88a707341044b49b0e24a9bac8bcc4.png
[640_wx_fmt_png 2]: /images/20220122/709de61dbf1847f19a0e9989679f2b1c.png
[640_wx_fmt_png 3]: /images/20220122/9fdb2c5ec0094726845423f38bfa6383.png
[640_wx_fmt_png 4]: /images/20220122/6f0e659a04d6458a943c99643ca781ac.png
[640_wx_fmt_png 5]: /images/20220122/2ceb2648148743bf9aa7756a1be7bd6b.png
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzI2OTA3NTk3Ng==&mid=2649284622&idx=1&sn=508b6434fe7a55e76866f330a8f45ea4&chksm=f2f99369c58e1a7f9d0b116e1efbcb171a5a5a32cbe6a6a95f15e749ca9cf889e6a2f0c268ab&scene=21#wechat_redirect
[Link 3]: http://mp.weixin.qq.com/s?__biz=MzI2OTA3NTk3Ng==&mid=2649284651&idx=1&sn=df0b31e5476919d30743a85f4938c3c1&chksm=f2f9934cc58e1a5ae0b97ce3d297f6e0ea042454851db66532714cddf456f9aaecb3f0fcda20&scene=21#wechat_redirect
[640_wx_fmt_jpeg]: /images/20220122/39a708cd49044236a7ca7ef05fa3e045.png