原题链接：http://ac.jobdu.com/problem.php?pid=1431
- 题目描述：
给你n个整数，请按从大到小的顺序输出其中前m大的数。
- 输入：
每组测试数据有两行，第一行有两个数n,m(0<n,m<1000000)，第二行包含n个各不相同，且都处于区间[-500000,500000]的整数。
- 输出：
对每组测试数据按从大到小的顺序输出前m大的数。
- 样例输入：
5 3
3 -35 92 213 -644
- 样例输出：
213 92 3
题解：
寻找前m大数与寻找第m大数是同一问题，直接对n个数排序肯定是会超时的，这类问题有很多解法，本题采用小顶堆完成。小顶堆的堆顶元素就是最大m个元素中最小的一个。初始可以将每个值设得尽可能小(比n个数的任何数都小)，然后每次考虑一个数X，如果X比堆顶元素小，则不需要改变原来的堆，如果X比堆顶元素大，则需要用X替换堆顶元素，并同时调整堆结构。这个调整的过程的时间复杂度为O(logm)。
#include <cstdio>
#include <stdlib.h>
#include <algorithm>
using namespace std; int n,m;
int arr[];
int heap[]; bool cmp(int a,int b)
{
if(a>b)
return true;
else
return false;
}
int main()
{
freopen("sort.in","r",stdin);
freopen("sort.out","w",stdout);
int p,q;
while(scanf("%d %d",&n,&m)!=EOF)
{
for(int i=; i<m; i++)
heap[i] = -; for(int i=; i<n; i++)
{
scanf("%d",&arr[i]);
if(arr[i]>heap[])
{
heap[] = arr[i];
p = ;
while(p<m)
{
q = *p +;
if(q >= m)
break;
if((q<m-) && (heap[q+]<heap[q]))
q =q+;
if(heap[q]<heap[p])
{
swap(heap[p],heap[q]);
p = q;
}
else
break;
}
}
} sort(heap,heap+m,cmp);
for(int i=; i<m; i++){
printf("%d",heap[i]);
if(i<m-)
printf(" ");
}
printf("\n");
}
return ;
}