从1亿个整数中找出最大的1万个

#include <iostream> #include <ctime> #include <functional> #include "algo.h" #include <fstream> #include <algorithm> using namespace std; const unsigned int TEST_TIME = 1; int main() { int* BigArr = new int[ BIG_ARR_SIZE ]; srand( time( NULL ) ); clock_t begin_time, end_time; double sum; unsigned int i; //调用STL自带 pop_heap 和push_heap函数 for( i = 0; i < TEST_TIME; ++i ) { fill_arr( BigArr, BIG_ARR_SIZE ); begin_time= clock( ); //建最小堆 make_heap(BigArr,BigArr+RES_ARR_SIZE,greater_equal<int>()); for(int j=RES_ARR_SIZE;j<BIG_ARR_SIZE;j++) { //大于最小堆根节点，岀堆，交换值，再入堆 if(BigArr[0]<BigArr[j]) { pop_heap(BigArr,BigArr+RES_ARR_SIZE,greater_equal<int>()); swap(BigArr[RES_ARR_SIZE-1],BigArr[j]); push_heap(BigArr,BigArr+RES_ARR_SIZE,greater_equal<int>()); } } end_time=clock( ); sum= end_time - begin_time; } std::cout << "solution_1 used time: "<< sum << std::endl; //模板adjust_heap函数 for( i = 0; i < TEST_TIME; ++i ) { fill_arr( BigArr, BIG_ARR_SIZE ); begin_time= clock( ); //建最小堆 make_heap(BigArr,BigArr+RES_ARR_SIZE,greater_equal<int>()); for(int j=RES_ARR_SIZE;j<BIG_ARR_SIZE;j++) { //调整顶端元素 if(BigArr[0]<BigArr[j]) { adjust_heap(BigArr,0,(int)RES_ARR_SIZE,j,*(BigArr+j),greater<int>() ); } } end_time=clock( ); sum= end_time - begin_time; } cout << "solution_2 used time: "<< sum << endl; //完全特例化的adjust_heap函数 for( i = 0; i < TEST_TIME; ++i ) { fill_arr( BigArr, BIG_ARR_SIZE ); begin_time= clock( ); //建最小堆 make_heap(BigArr,BigArr+RES_ARR_SIZE,greater_equal<int>()); for(int j=RES_ARR_SIZE;j<BIG_ARR_SIZE;j++) { //调整顶端元素 if(BigArr[0]<BigArr[j]) { adjust_heap(BigArr,0,(int)RES_ARR_SIZE,j,*(BigArr+j)); } } end_time=clock( ); sum= end_time - begin_time; } cout << "solution_3 used time: "<< sum << endl; delete []BigArr; return 0; }