堆排序在工业届应用很广泛，在实际应用中的top-k问题很适合用堆的思想完成。
I、上帝视角看堆排序
堆排序就是利用堆（常用大顶堆）进行排序的方法。它的基本思想就是，将待排序的序列构成一个大顶堆。此时，整个序列的最大值就是对顶的根结点。将它移走（与堆尾元素交换），此时末尾元素就是最大值，然后将剩余的n-1个序列重新构成了一个堆，这样就得到n个元素中的次大值，如此反复执行，便得到一个有序序列。
上面的描述可以用下面的示意图表示：
堆排序示意图1
堆排序示意图2
II、堆排序实现
对于堆排序的实现，主要需要考虑两个问题：
1、如何由一个无序序列构建一个堆；
2、调整剩余元素使之构成一个新堆；
#include <iostream>
#include <vector>
using namespace std;
void adjustHeap(vector<int>& vec, int p, int len) {
int curParent = vec[p];
int child = 2*p+1; //左孩子
while (child < len) { //有孩子
if (child + 1 < len && vec[child] < vec[child+1]) { //比较左右孩子
child++; //变为右孩子
}
if (curParent < vec[child]) {
//没有讲curParent赋值给孩子是因为还要迭代子树
//如果其孩子中有大的，会上移，curParent还要继续下移
vec[p] = vec[child];
p = child; //向下迭代
child = 2*p + 1; //更新迭代坐标
}
else break;
}
vec[p] = curParent;
}
void heapSort(vector<int>& vec, int len) {
//建立堆，从最底层的父结点开始
for (int i = len/2-1; i >= 0; --i)
adjustHeap(vec, i, len);
for (int i = len - 1; i >=0; --i) {
swap(vec[0], vec[i]);
adjustHeap(vec, 0, i); //调整剩余元素的建堆
}
}
int main()
{
vector<int> vec = {6,3,4,5,1,7};
heapSort(vec, vec.size());
for (auto i : vec)
cout << i << ",";
return 0;
}
【参考】
[1] 《大话数据结构》
欢迎转载，转载请注明出处wenmingxing 堆排序初探
