一亿个数找最大的1000个数,要求效率高占用内存少。函数原型为:find_max_data(int* source_data, int* max_data),其中source_data是存放一亿个数的数组,max_data用于存放其中最大的1000个数。
#include<iostream>#include<vector> using namespace std;
#include<string.h> #include<assert.h> void
down(int * data,int start,int end) { int i=start; int j=2*i+1;
int temp= data[i]; while(j<=end) {
if(j+1<end && data[j] >data[j+1]) j++;
if(data[j] <temp) {
data[i]=data[j]; i=j;
j=2*i+1; } else {
break; } } data[i]=temp; } void
min_heap(int * data,int n) { for(int
i=(n-1)/2;i>=0;i++) { down(data,i,n); } }
void find_max_data(int* source_data,int * max_data) {
memcpy(max_data,source_data,sizeof(int)*1000); //调整最小堆
min_heap(data,1000); for(i=1000;i<1000000000;i++) {
int val = data[0]; if(data[0] <data[i])
{ data[0]= data[i];
down(data,0,n); } } } void main() {
find_max_heap(source_data,max_data); }