[Microsoft面试]查找最小的k 个元素

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

This isa very traditional question...O(nlogn): cat I_FILE | sort -n | head -n KO(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-1times.So traditional that I don’t want to write the codes...Only gives the siftup and siftdown function./***@paramithe index of the element in heap a[0...n-1] to be sifted upvoid 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 (j<n && a[j]<a) i = j;    if (a < a[p]) swap(a, i, p);    i = p;  } }void siftdown(int a[], int i, int n) {   while (2*i+1<n){    int l=2*i+1;    if (l+1<n && a[l+1] < a[l]) l++;    if (a[l] < a) swap(a, i, l);    i=l;  }}