题目描述


：在好几亿个数据中找出最大或最小的K个数。


分析：这几亿的数据肯定不能一起加载到内存中去，更不能对这些数据直接进行排序，因此我们这里讲用数据结构中的堆来解决这个问题。


假定这里要从100000个数据中找出最大的100个数据，这样是为了描述方便，我们这里直接用一个数组来存储这个100000个数据，如果数据多达好几亿，则只需将这些数据放入文件中进行读写即可，这里为了描述问题方便就这样假定。


步骤：

取出这些数据中前100个数据，然后用这些数据建立一个小堆；

从第101个数据开始，每读取一个数据，就与堆顶的元素进行比较，如果该数据大于堆顶的数据，则将堆顶的数据替换为该数据，并对这个小堆进行调整。

重复步骤2，等到所有数据都取完后，则留下的这个堆中的100个元素，就是我们要得到的最大的100个数。


代码如下：

#pragmaonce#include<iostream>#include<time.h>usingnamespacestd;#defineN100000//N个数据#defineK100//最大或最小数据的个数//仿函数，可以选最大的K个数，也可以选最小的K个数template<classT>structLess{booloperator()(constT&num1,constT&num2){returnnum1<num2;}};template<classT>structGreater{booloperator()(constT&num1,constT&num2){returnnum1>num2;}};template<classT,classcom=Less>//默认建小堆classHeap{public:Heap(constT*a,size_tsize):MaxOrMinK(newT[size]),_size(size){for(size_ti=0;i<_size;++i){MaxOrMinK[i]=a[i];}}~Heap(){if(_size>0)delete[]MaxOrMinK;}voidCreatHeap()//建堆,(小/大){for(inti=(_size-2)/2;i>=0;--i){AdjustDown(MaxOrMinK,_size,i);}}voidGetK(constT*array,size_tsize)//从array中选出最大(或最小)的K个数{for(inti=K;i<size;++i){if(com()(MaxOrMinK[0],array[i])){MaxOrMinK[0]=array[i];AdjustDown(MaxOrMinK,_size,0);}}}voidPrint(){if(_size>0){for(size_ti=0;i<_size;++i){cout<<MaxOrMinK[i]<<endl;}}}protected:voidAdjustDown(T*&a,size_tsize,size_troot){size_tchild=root*2+1;//计算左孩子while(child<size){if(child+1<size&&com()(a[child+1],a[child])){++child;}if(com()(a[child],a[root])){std::swap(a[root],a[child]);root=child;child=root*2+1;}else{break;}}}private:T*MaxOrMinK;size_t_size;};voidTest1(){intrandNum[N];srand(time(NULL));for(inti=0;i<N;++i){inttmp=rand()%10000;randNum[i]=tmp;//产生N个10000以内的随机数}Heap<int,Less<int>>get_K(randNum,K);//小堆选最大的K个数get_K.CreatHeap();get_K.GetK(randNum,N);get_K.Print();}voidTest2(){intrandNum[N];srand(time(NULL));for(inti=0;i<N;++i){inttmp=rand()%10000;randNum[i]=tmp;//产生N个10000以内的随机数}Heap<int,Greater<int>>get_K(randNum,K);//大堆选最小的K个数get_K.CreatHeap();get_K.GetK(randNum,N);get_K.Print();}