/*****************************复杂度：

***************************/#include<iostream>#include<assert.h>#include<vector>#include<stdlib.h>#include<time.h>usingnamespacestd;#defineN1000#defineK100voidAdjustDown(int*a,size_troot,size_tsize){//向下调整小堆size_tparent=root;size_tchild=parent*2+1;while(child<size){if(child+1<size&&a[child]>a[child+1]){++child;}if(a[parent]>a[child]){swap(a[parent],a[child]);parent=child;child=parent*2+1;}else//注意不满足交换条件时跳出本次循环{break;}}}voidGetTopk(constvector<int>&Vnumber,intn,intk)//N个数中找最大的前k个数--小堆实现{assert(n>k);int*TopkArray=newint[k];//通过前k个元素建立含有k个元素的堆for(size_ti=0;i<k;i++){TopkArray[i]=Vnumber[i];}for(inti=(k-2)/2;i>=0;--i)//建小堆{AdjustDown(TopkArray,i,k);}//从第k个元素开始到第n个元素分别与堆顶元素进行比较，较大数据入堆顶，再对整个堆进行下调，使堆顶存放最小元素（小堆）for(size_ti=k;i<n;++i){if(Vnumber[i]>TopkArray[0]){TopkArray[0]=Vnumber[i];AdjustDown(TopkArray,0,k);}}size_tcount=0;for(size_ti=0;i<k;++i)//打印k个最大数据，即堆中所有元素{cout<<TopkArray[i]<<"";++count;if(count%10==0){cout<<endl;}}cout<<endl;delete[]TopkArray;//注意释放TopkArray所占的内存TopkArray=NULL;}voidCreateVnumber(vector<int>&Vnumber)//创建N个数{srand((unsignedint)time(NULL));//srand(time(0));Vnumber.reserve(N);for(size_ti=0;i<N;i++){Vnumber.push_back(rand()%1000);//产生N个随机值}for(size_ti=K;i<N;++i){Vnumber[i]*=100;}}intmain(){vector<int>Vnumber;CreateVnumber(Vnumber);GetTopk(Vnumber,N,K);//intlength=Vnumber.size();//for(inti=0;i<length;i++)//{//cout<<Vnumber[i]<<"";//}return0;}