最小的k个数

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;

//全排序
//复杂度O(n*logn)
vector<int> Full_sorting(vector<int> input, int k) {
   vector<int> res;
   if(input.empty()||k>input.size()||k<=0) return res;

   sort(input.begin(),input.end());

   for(int i=0;i<k;i++)
       res.push_back(input[i]);

   return res;

}

//BFPRT算法，在时间复杂度O(N)内，从无序的数组中找到第k小的数
//再用快排，做一次选择排列，相当于改进版本的快速排序（初始元素不选第一个，而尽量选择中间的）
//适合非海量数据
//可以证明复杂度O(n)
//见[2]


//最大堆
//建堆复杂度O(k),重建一次堆O(logk),重复n-k次，总复杂度O（k+(n-k)*logk)；
//数量级O(n*logk)
vector<int> Max_Heap(vector<int> input, int k) {
   int len=input.size();
   if(len<=0||k>len||k<=0) return vector<int>();

   vector<int> res(input.begin(),input.begin()+k);
   //for (int i = 0; i < k; i++) result.push_back(input[i]);
   make_heap(res.begin(),res.end());
   for(int i=k;i<len;i++){
       if(input[i]<res[0]){
           pop_heap(res.begin(),res.end());
           res.pop_back();
           res.push_back(input[i]);
           push_heap(res.begin(),res.end());
       }
   }
   sort_heap(res.begin(),res.end());
   return res;
}

//也是用堆，不过是对整个数据建一个最小堆（O（n）），然后取出堆顶元素，
//每取完一次更新一次堆（O（logn）），取K次，所以总的复杂度是O（n+K*logn)；
//数量级上与最大堆不存在差别，但其空间复杂度更大(n>m)
//所以综合来讲，最大堆解决这种方法比最小堆有优势
//算法改进：每次取走堆顶元素更新堆时，正常是把堆中最后一个元素放到堆顶，
//然后调整堆将其下调到他应该在的位置。改进后，此元素不用下调到他原所应该在的位置，
//而是下调顶多K次就可以了。

//红黑树 原理上讲没看出和最大堆不同，写法上区别，可能因为对红黑树不了解
//复杂度O(nlogk)
vector<int> Red_and_black_Trees(vector<int> input, int k) {
   int len=input.size();
   if(len<=0||k>len||k<=0) return vector<int>();

   //multiset<int> sbt;         //默认小到大
   //multiset<int, greater<int> > sbt; //定义大到小
   //sbt.empty()      //判断是否有元素
   //sbt.insert(x)    //插入x元素
   //sbt.erase(x);    //删除x元素
   //sbt.size(x)      //x元素有多少个
   //sbt.begin()       //第一个元素*(sbt.begin())
   multiset<int, greater<int> > leastNums;
   vector<int>::iterator vec_it=input.begin();
   for(;vec_it!=input.end();vec_it++){
       if(leastNums.size()<k)
           leastNums.insert(*vec_it);
       else{
           multiset<int, greater<int> >::iterator greatest_it=leastNums.begin();
           if(*vec_it<*(leastNums.begin())){
               leastNums.erase(greatest_it);
               //leastNums.erase(*greatest_it);也可以
               //删除时均ok，插入时必须加*
               leastNums.insert(*vec_it);
           }
       }
   }
   return vector<int>(leastNums.begin(),leastNums.end());
}

int main()
{
    int a[] = {10,20,30,5,15};
    vector<int> v(a,a+5);
    vector<int> r;
    vector<int>::iterator it;
    int k=3;
    //r = Red_and_black_Trees(v,k);
    //r = Full_sorting(v,k);
    r = Max_Heap(v,k);

    for(it=r.begin();it!=r.end();it++){
     cout << *it << ' ';
    }
    cout << endl;
    return 0;
}

参考：

[1] https://www.nowcoder.com/questionTerminal/6a296eb82cf844ca8539b57c23e6e9bf
[2]https://www.jianshu.com/p/5ad9ca0e3cf6