7-38 寻找大富翁 (25 分)
胡润研究院的调查显示，截至2017年底，中国个人资产超过1亿元的高净值人群达15万人。假设给出N个人的个人资产值，请快速找出资产排前M位的大富翁。
输入格式:
输入首先给出两个正整数N（≤106）和M（≤10），其中N为总人数，M为需要找出的大富翁数；接下来一行给出N个人的个人资产值，以百万元为单位，为不超过长整型范围的整数。数字间以空格分隔。
输出格式:
在一行内按非递增顺序输出资产排前M位的大富翁的个人资产值。数字间以空格分隔，但结尾不得有多余空格。
输入样例:
8 3
8 12 7 3 20 9 5 18
输出样例:
20 18 12
分析：
看了几篇题解，基本不是开了十万的数组，就是优先队列，其实没有必要，
注意n，m的范围，开一个15（其实10就可以了，防止越界罢了）数组，
采用小顶堆，输入的值依次与堆顶的元素进行比较，
小于或等于堆顶元素则必然不在最终答案里
（因为按小顶堆排序，堆顶为堆最小元素），
如果大于堆顶，则取代堆顶元素，并重新排序。
输入结束，将数组内元素重新排序，
这样做的原因是堆的逻辑结构类似于树，叶子结点的元素排列并不是严格递增的。
例如:
此时输入19
则堆变为：
则输出为
19 20 18
不符合期望输出。
因此最后需重新排序。
最后注意n<m的情况。
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,k;
int a[15];
void down(int x){//堆排序模板
int t=x;
if(2*x<=k&&a[t]>=a[2*x])t=2*x;
if(2*x+1<=k&&a[t]>=a[2*x+1])t=2*x+1;
if(x!=t){
swap(a[t],a[x]);
down(t);
}
}
int main(){
cin>>n>>m;
k=(n>=m?m:n);//判断n，m大小
for(int i=1;i<=k;++i)cin>>a[i];
for(int i=k/2;i;i--)down(i);
n-=k;
while(n--){
int x;
scanf("%d",&x);
if(x<=a[1])continue;
else {
a[1]=x;
down(1);
}
}
sort(a+1,a+k+1);
cout<<a[k];
for(int i=k-1;i;--i)cout<<" "<<a[i];
cout<<endl;
return 0;
}
总结：
堆排序的模板题，并不难，关键在代码的优化。