top K问题 （从1000个数据中找到k个最大数据）

思路： 可先创建一个数组topK[k],将1000中的前k个数据放入数组topK中，将topK中的数据建小堆，则可保证堆的第一个元素是最小的，将第k个元素与堆中第一个元素比较，若大于，则交换。对堆进行重新建小堆，取第k+1个元素与堆中第一个元素比较，以此类推，直至1000-k个元素比较完。则此时堆中的元素就是k个最大数据。

const int N = 1000; const int K = 100; void AdjustDown(int topK[],int parent) //建小堆 { int child = 2*parent+1; while(child < K) { if(child+1 < K && topK[child+1] < topK[child]) { ++child; } if(topK[child] < topK[parent]) { swap(topK[child],topK[parent]); parent = child; child = 2*parent+1; } else { break; } } } void GetTopK(int a[],int topK[]) { assert(a); int i = 0; for(i=0;i<K;++i) //将a的前K个元素放入数组中 { topK[i] = a[i]; } for(i=(K-2)/2;i>=0;--i)//对前K个元素建小堆 { AdjustDown(topK,i); } for(i=K;i<N;++i) { if(a[i] > topK[0]) //将K个元素之后的每个元素和堆的第一个元素(最小元素)比较 { swap(a[i],topK[0]);//若比第一个元素大，则交换 AdjustDown(topK,0);//对新堆重新建小堆 } } } 测试代码： void Test2() { int topK[K]; int a[N]; srand(time(0)); //随机数种子 for(int i=0;i<N;++i) { a[i] = rand(); //随机数 } GetTopK(a,topK); for(int i=0;i<K;i++) { cout<<topK[i]<<" "; } }

原文地址：http://10810429.blog.51cto.com/10800429/1771392