排序中的堆排序一直没去看，然后去百度面试问了topN的算法，小数据集。我在写代码的过程中用了STL中的set保存了最大的N个数，然后取得第N+1个数，与set中的第一个数比较，如果大于它，则擦除第一个数，插入第N+1个数。然后面试官说，这个方法肯定不是他想要的。好吧，我猜他是想要我用建堆写代码，没搞定，回来赶紧恶补一下。
简单选择排序没有把前一趟的比较结果保留下来，这样在后一趟选择时，反复对前一趟已经做过的比较又重做了一遍，堆排序就是针对这点对简单选择排序进行了改进。首先，什么是堆？堆是具有下列性质的完全二叉树。
（1）小根堆：每个节点的值<=左右孩子节点的值
（2）大根堆：每个节点的值>=左右孩子节点的值
堆的存储结构：对于一个具有n个记录的堆，可以用如下方法，由数组r[]来存放它：
（1）根节点存放在r[1]；
（2）假定节点x存放在r[i],若它有左孩子节点，则其左孩子节点存放在r[2i]，如果它有右孩子节点，则其右孩子节点存放在r[2i+1]
建堆的过程其实关键就是堆的调整过程，小根堆的筛选过程是：从最后一个分支节点开始逐个向上筛选，直到根节点结束，这样从最后一棵子树开始使其符合堆的性质，迭代地使整个树符合堆的性质。若堆排序的长度为n，则最后一个分支节点的编号为[n/2]。
堆排序：根据堆的性质，堆的根节点总是堆中的最小元素（小根堆），所以将根节点逐个输出，并令剩下的部分重新恢复堆的性质，这样就可以实现排序。堆排序的具体过程如下：
（1）将待排序的元素构造一个堆
（2）输出堆顶元素
（3）将堆中最后一个元素移至堆顶，直到堆中只有一个元素。
反复执行后两个步骤，直到堆中只有一个元素。
C++程序代码如下:
/*小根堆*/
#include <iostream>
using namespace std;
void HeapSift(int A[], int k, int n) {
int i = k, j = 2*i;
while (j <= n) {
if (j<n && A[j]>A[j+1]) { //筛选的节点
++j;
}
if (A[i] < A[j]) { //符号小根堆的条件，结束
break;
}
else {
swap(A[i], A[j]);
i = j;
j = 2*i;
}
}
}
int main() {
int i;
int n;
cin >> n;
int *f = new int[n+1];
for (i=1; i<=n; ++i) {
cin>>f[i];
}
for (i=n/2; i>=1; --i) { //建堆
HeapSift(f, i, n);
}
for (i=1; i<n; ++i) {
cout << f[1] << " ";
swap(f[1], f[n-i+1]);
HeapSift(f, 1, n-i);
}
cout << f[1];
cout << endl;
return 0;
}
由此可以推断出，topN的算法需要建小根堆，代码如下：
#include <iostream>
using namespace std;
void HeapSort(int f[], int k, int n) {
int i = k, j = 2*i;
while (j<=n) {
if (j<n && f[j]>f[j+1]) {
++j;
}
if (f[i] < f[j]) {
break;
}
swap(f[i], f[j]);
i = j;
j = 2*i;
}
}
void topN(int f[], int res[], int m, int n) {
int i;
for (i=1; i<=n; ++i) {
res[i] = f[i];
}
if (i<=n) {
return;
}
for (i=n/2; i>=1; --i) {
HeapSort(res, i, n);
}
for (i=n+1; i<=m; ++i) {
if (res[1] < f[i]) { //堆顶小于待比较的数
res[1] = f[i];
}
HeapSort(res, 1, n);
}
}
int main() {
int m,n;
cin >> m >> n;
int *f = new int[m+1];
int *res = new int[n+1];
int i;
for (i=1; i<=m; ++i) {
cin >> f[i];
}
topN(f, res, m, n);
for (i=1; i<=n; ++i) {
cout << res[i] << " ";
}
cout << endl;
}