查找最小的k个元素

题目：输入n个整数，输出其中最小的k个。

例如：输入1，2，3，4，5，6，7和8这8个数字，则最小的4个数字为1，2，3和4


思路：用一个k的容器，先放入K个数，然后接下来总是把最大数给踢出去。

用大顶堆，或者红黑树，大顶堆，大顶堆在O(1)得到已有的k个数字中的最大值，但需要O(logk)时间完成删除以及插入操作。红黑树通过把结点分为红、黑两种颜色并根据一些规则确保树是平衡的，从而保证在红黑树中查找、删除和插入操作都只需要O(logk)

public void getMinK(int[] arr,int k){
   List<Integer> stack= new ArrayList<Integer>(); //里面放最小的k个数
   for(int i=0;i<arr.length;i++){
   }

}

-------------------------------------------------------------------------------------------

#include <stdio.h>
//已知（k1,k2……，kn）是堆，试写一个算法将（k1,k2,……，kn,kn+1）调整为堆。
//按此思想写一个从空堆开始一个一个填入元素的建堆算法
//（题示：增加一个k n+1后应从叶子向根的方向调整）
#define length 6
void HeadSort(int a[],int n);
void HeadAdjust(int a[],int s, int m);
void HeadAdjust(int *a,int head, int tail) {  
    int temp;
    temp = a[head];           //若s=2 ,则rc = a[1]
    for ( int j= 2*head; j <= tail; j= 2*j) {
        if( j<tail && a[j]<a[j+1])
            ++j;
        if( temp > a[j])  
            break;
        a[head] = a[j];
        head = j;          
    }
    a[head] = temp;  
//打印*********************
    for(int i = 0 ; i < length; i++) {
            printf("%d ",a[i]);
    }
    printf("/r/n");
  
//打印*********************打印结束
} //    HeadAdjust
void HeadSort(int *a,int n) {
    int i;
    int tmp;
    for( i = length/2  ; i > 0; --i) {
        HeadAdjust(a,i,length);
    }
//打印*********************
    for(i = 0 ; i < length; i++) {
        printf("%d ",a[i]);
    }
    printf("/r/n");
//**********************打印结束
    tmp = a[0];
    a[0] = a[length-1];
    a[length-1] = tmp;
//打印**********************  
    for(i = 0 ; i < length; i++) {
        printf("%d ",a[i]);
    }
    printf("/r/n");
//打印*********************打印结束
    for(i = length-1; i>1; --i) {//////////////
        printf("i's value:%d/n",i);
        HeadAdjust(a,0,i);
        tmp = a[0];
        a[0] = a[i];
        a[i] = tmp;  
    }
    printf("i's value:%d/n",i);
}
int main() {
  
    int n ;
    int a[1000] ;
    printf("Input the Number you want to Sort :");
    scanf("%d",&n);
    printf("Please Input the values :");
    for(int i=0;i<n;++i)
        scanf("%d",&a[i]);//输入时,不能在"%d"内多出任何空格,否则需要多敲一个字符********************Important
    printf("/r/n");
    HeadSort(a,n);
    for(i=0;i<n;++i)
        printf("%d ",a[i]);
    printf("/r/n");
    return fals