最小的K个数

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。

用堆排序来做。

 1 class Solution {
 2 public:
 3     vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
 4         vector<int> s;
 5         vector<int> res;
 6         int n=input.size();
 7         if(k<0||n<k) return res;
 8         for(int i=0;i<n;i++){
 9             s.push_back(input[i]);
10             
11             stackinsert(s);
12         }
13         for(int i=0;i<k;i++){
14             swap(s[0],s[s.size()-1]);
15             res.push_back(s[s.size()-1]);
16             s.pop_back();
17             stackdelete(s);
18         }
19         return res;
20     }
21 private:
22     void stackinsert(vector<int>& s){
23         int n=s.size();
24         while(n>1){
25             if(n/2>0&&s[n-1]<s[n/2-1]){
26                 swap(s[n-1],s[n/2-1]);
27                 n=n/2;
28                 continue;
29             }
30             return;
31         }
32     }
33     void stackdelete(vector<int>& s){
34         int n=s.size();
35         int i=1;
36         while(i<n){
37             int min=i;
38             if(((2*i)<=n)&&s[i-1]>s[2*i-1])
39                 min=2*i;
40             if(((2*i+1)<=n)&&s[min-1]>s[2*i+1-1])
41                 min=2*i+1;
42             if(i==min)
43                 return;
44             else{
45                 swap(s[i-1],s[min-1]);
46                 i=min;
47             }
48         }
49     }
50 };