第三章：寻找最小的k个数

寻找最小的k个数
题目描述：5.查找最小的k个元素
题目：输入n个整数，输出其中最小的k个。
例如输入1，2，3，4，5，6，7和8这8个数字，则最小的4个数字为1，2，3和4。

堆实现可见：简洁的heap代码

#include <iostream>
#include <windows.h>
#include <algorithm>
#include <numeric>
#include <string>
#include <array>
#include <vector>
#include <functional>
#include <hash_set>
#include <ctime>
using namespace std;

#define N 20//最大的N个数
//第一种方法，维护N+1个元素的小顶堆
//O(NlogK)
void f1(){
	//freopen("C:\\in.txt","r",stdin);
	vector<int> t(10000);
	srand((unsigned)time(NULL));
	generate(t.begin(),t.end(),[](){return rand()%10000;});
	
	make_heap(t.begin(),t.begin()+N+1,greater<int>());
	for(auto it=t.begin()+N+1;it!=t.end();){
		push_heap(t.begin(),t.begin()+N+1,greater<int>());
		pop_heap(t.begin(),t.begin()+N+1,greater<int>());
		it=t.erase(t.begin()+N);
	}
	for_each(t.begin(),t.end(),[](int i){cout<<i<<endl;});
}
//第二种方法：整个建堆，pop K次
//O(N+KlogN)
void f2(){
	vector<int> t(1000000);
	srand((unsigned)time(NULL));
	generate(t.begin(),t.end(),[](){return rand()%10000;});
	
	make_heap(t.begin(),t.end());//对所有元素建大顶堆
	for(int i=0;i<N;i++){
		cout<<t.front()<<endl;
		pop_heap(t.begin(),t.end());
		t.pop_back();
	}
}
void Test(){
	f2();
}
int main()    
{    
    LARGE_INTEGER BegainTime ;    
    LARGE_INTEGER EndTime ;    
    LARGE_INTEGER Frequency ;    
    QueryPerformanceFrequency(&Frequency);    
    QueryPerformanceCounter(&BegainTime) ;    
    
    //要测试的代码放在这里   
    Test();   
     
    QueryPerformanceCounter(&EndTime);   
    
    //输出运行时间（单位：s）   
    cout << "运行时间（单位：s）：" <<(double)( EndTime.QuadPart - BegainTime.QuadPart )/ Frequency.QuadPart <<endl;    
    
    //system("pause") ;    
    return 0 ;    
}

第三章：寻找最小的k个数

原文：http://blog.csdn.net/starcuan/article/details/19031237