面试中的排序算法（Part 3）
今天来谈一种十分重要的堆排序的算法，其在STL中的数据结构也就是Priority_Queue。也是一种十分高效的排序方式，虽然其算法模型为二叉树结构，但是可以使用数据进行模拟这个二叉树的结构和相应的函数操作！
大根堆和小根堆
堆树的定义如下：
- 堆树是一颗完全二叉树
- 堆树的当前节点总是不大于或者不小于其孩子节点的值，如果不大于其孩子节点，叫做小根堆。如果不小于其孩子节点，叫做大根堆
- 堆中每个结点的子树也都是堆树结构
大根堆和小根堆的应用如下图所示，可以根据你需要什么样的排序方式来使用不同的堆结构！
大根堆和小根堆
那么我们知道了堆的特性之后，我们就可以使用堆的结构对一个列表进行排序，通常为了编程和实现简单，我们会使用数组来模拟堆结构，假设原始数组为a={4,1,3,2,16,9,10,14,8,7}，那么它对应的堆结构（大根堆）为如下图所示：
大根堆结构
建立堆以及调整堆
那么我们如何使用数组来表述堆这种结构呢？这里面有一个规律，经过层次遍历后将一个二叉树变成一个数组，如果当前节点的索引值为i，且0<=i<N（从零开始），那么
- 父节点索引为：(i-1) / 2，其中(0-1) / 2 = 0
- 左节点索引为：2*i+1，如果超过索引，则没有左节点
- 右节点索引为：2*i+2，如果超过索引，则没有右节点
当我们清楚的知道这些关系后，我们就可以通过一个数组建立起一个大根堆，核心思路为：
边建立边调整，我们遍历整个数组，遍历的同时比较当前节点（索引为i）和对应的父节点（索引为(i-1)/2），如果没有根节点大，那么就交换两个值，直到遍历完整个列表！
// 建立一个大根堆，时间复杂度为O(N)=O(log1)+O(log2)+...+O(logN)
void heapInsert(vector<int>& list, int index) {
while (list[index] > list[(index - 1) / 2]) { // (0-1)/2 = 0
swap(list[index], list[(index - 1) / 2]);
index = (index - 1) / 2;
}
}当我们的大根堆建立完毕后，如果还需要一个调整堆的函数，也就是说如果一个堆结构发生了变化，比如某一个值的大小发生了变化，那么我们怎样去维持这个结构仍然是大根堆？这是一个heapify的过程！
我们假设索引0的值发生了变化，那么我们首先需要得到其孩子节点较大的值，然后与这个变化后的值比较，如果变化后的值较小，那么就交换两者，接着循环遍历！否则直接退出（由于除了变化的节点相关的，其他节点都继续维持大根堆结构，所以不用判断了）
// 改变一个值，仍然使其为大根堆（将数组看做完全二叉树）
void heapify(vector<int>& list, int index, int heapSize) {
int left = index * 2 + 1;
while (left < heapSize) {
int largest = left + 1 < heapSize && list[left + 1] > list[left] // left+1为右孩子的索引
? left + 1 : left;
largest = list[largest] > list[index] ? largest : index;
if (largest == index) {
break;
}
swap(list[index], list[largest]);
index = largest;
left = index * 2 + 1;
}
}堆排序
当我们得到了这两种堆的操作后，我们就可以完成我们的堆排序了，算法思路很简单，因为难得我们已经说过了！
堆排序流程图
算法流程：首先对整个列表建立大根堆，则索引0的位置为最大值（毋容置疑），然后将其和最后一个值交换，接着让堆大小减一（已经确定了一个数的位置），由于索引0的值发生了变化，我们需要重新检查和调整其为大根堆（heapify的过程）。接着循环整个过程就可以了，直到堆大小减为0停止！
// 六、堆（大根堆）排序算法
void HeapSort(vector<int>& list) {
if (list.size() < 2) {
return;
}
for (int i = 0; i < list.size(); i++) {
heapInsert(list, i);
}
int heapSize = list.size();
while (heapSize > 0) {
swap(list[0], list[--heapSize]);
heapify(list, 0, heapSize);
}
}资源分享
完整测试文件（C++版）,文件名为：常见排序算法（重点），请关注我的个人公众号 （算法工程师之路），回复"左神算法基础CPP"即可获得，并实时更新！希望大家多多支持哦~