我们在介绍《什么是优先队列》的时候就注意到，如果每次都删除堆顶元素，那么将会得到一个有序的数据。因此，我们可以利用二叉堆来对数据进行排序。 点我查看本文代码地址。
堆排序分析
通过前面的学习我们可以看到，如果构建一个二叉堆，最后每次从堆顶取出一个元素，那么最终取出元素就是有序的，不过如果要用来对数据按照从小到大排序，就不是构造小顶堆，而是大顶堆了，即堆顶元素大于等于其左右儿子节点。总结堆排序思路如下：
以O(N)时间复杂度构建N个元素的二叉堆
以O(logN)时间复杂度删除一个堆顶元素，N个元素时间复杂度为O（NlogN）
由于删除一个堆顶元素时，就会空出一个位置，为了节省空间，将删除的堆顶元素放到数组末尾
当堆为空时，完成排序
由于数组元素从下标0开始，因此每个位置必须利用好。假设堆顶元素位置为i,那么左右儿子节点位置分别为2i+1,2i+2
实例分析
根据前面的分析，我们来看一个具体的例子。假设我们要对
进行排序。
该数据构成的原始二叉树如下：
构建二叉堆
为了能够使得数组所有元素满足堆的性质，即父节点大于等于儿子节点，我们需要从倒数第二层开始调整（为什么不是从最后一层？）。即调整8和10。
对于8来说，找到它的儿子节点中较大的一个，即35,将8和35交换后如下：
此时数组数据为：
对于10来说，它比左右儿子节点都大，因此不需要调整。
对于１来说，它的右儿子35最大，因此需要调整，和右儿子交换后如下：
此时数组数据为：
但是一次交换后，我们发现，１的左儿子还是比它大，因此交换它和较大的左儿子的位置，交换后如下：
此时数组数据为：
最终我们得到了满足堆性质的二叉堆了。
基于二叉堆的排序
在堆创建好后，每次取出堆顶元素，并且调整堆，把堆顶元素放在数组最后即可。
例如，对于前面创建好的堆，堆顶元素是35，我们取出第i（此时为1）个元素35，并把堆最后一个元素放在数组倒数第i个位置：
为了满足堆性质，我们需要调整堆顶元素，因为堆顶元素目前不满足堆性质，因此需要交换8和15的位置：
此时所有元素再次满足堆性质。
此时数组数据为：
对于其他元素也是同样的操作，因此不再赘述。
代码实现
根据上面的分析，关键代码实现如下：
voidadjust_ele(ElementType arr[],inti,intlength){intchild ; 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];elsebreak; }/*将i位置的元素放到正确的位置*/arr[i] = temp;}voidheap_sort(ElementType arr[],intlength){inti =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);}}
完整可运行代码地址： heapSort
运行结果：
beforesort:1108571535aftersort:1578101535
总结
结合我们前面介绍的优先队列，我们很容易理解堆排序，不过需要注意的就是位置0必须使用上。另外通过利用删除堆顶元素后空出来的位置，避免了另外申请数组内存来存放排序好的数组。建议自己修改完整可运行代码，来观察数据调整情况。
看我主页简介免费C++学习资源，视频教程、职业规划、面试详解、学习路线、开发工具
每晚8点直播讲解C++编程技术。
