首页 > 代码库 > 使用红黑树查找最小n个数,适合处理大数据

使用红黑树查找最小n个数,适合处理大数据

使用STL容器 multiset

代码:

#include <iostream>
#include <vector>
#include <set>
using namespace std;

typedef multiset<int,greater<int> > intSet;
typedef multiset<int,greater<int> >::iterator intIter;


void findMaxNum(const vector<int> &data,int k){
	intSet Max; 
	Max.clear();
	if(k < 1 || data.size() < k)
    	return ;
	vector<int>::const_iterator iter = data.begin();

	

	for(;iter != data.end();++iter){
		if(Max.size() < k){
			Max.insert(*iter);
			
		}else{
			intIter least=Max.begin();
			if((*iter) < *( Max.begin())){ //只能是begin()删除
				
				Max.erase(least);
				Max.insert(*iter);
			}

		}
	}
	for( intIter it = Max.begin(); it != Max.end();it ++){
		cout<<*it << "  ";
	}
}
int main()
{	
	
	vector<int> data;
	for(int i=0;i<1000;i++){
		data.push_back(i);
	}
	findMaxNum(data,10);
    return 0;
}

运行结果: