题目:输入n 个整数,输出其中最小的k 个。
例如输入1,2,3,4,5,6,7 和8 这8 个数字,则最小的4 个数字为1,2,3 和4。

ANSWER:
This is a very traditional question…
O(nlogn): cat I_FILE | sort -n | head -n K
O(kn): do insertion sort until k elements are retrieved.
O(n+klogn): Take O(n) time to bottom-up build a min-heap. Then sift-down k-1 times.
So traditional that I don’t want to write the codes…
Only gives the siftup and siftdown function.


 void siftup(int a[], int i, int n) {
     while (i>0) 
     { 
         int j=(i&1==0 ? i-1 : i+1); 
         int p=(i-1)>>1;  
         if (ji+1<n){
             int l=2*i+1;
             if (l+1<n && a[l+1] < a[l]) l++;
             if (a[l] < a[i]) swap(a, i, l);
             i=l;
               }
    }
 }