求最小的k个数有关问题

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

我的思路：利用二叉堆，构建一个容量为k的定长最小二叉堆，遍历数组，逐个将元素add进堆，完毕返回堆中所有元素即为最小的k个元素

    1 楼    LuckYes    2012-02-19              楼主如果用最小堆的话，最好用调整堆的方式来构建堆，这样效率更高以及更容易理解。
 public static void Sort(int[] a){
        int temp;
        int n = a.length;
        Display(a); 
        
        for(int i = n/2-1;i>=0;i--)                        //从非叶子节点开始
            Adjust(a, i, n);
                                        //初始化堆
        for(int i = n-1;i > 0;i--){
            temp = a[0];                                //交换根节点与最后一个叶子节点，要调整的范围减1
            a[0] = a[i];
            a[i] = temp;  
            Adjust(a, 0, i);                           //不断减小长度、 交换、调整
        }    
        Display(a);
    } 
    
    public static void Adjust(int[] a, int i, int n){     //调整函数，参数含义 代表从哪个节点开始跳着，n代表堆的长度范围
        int j = 2*i+1;                                    //从要调整的节点的子节点开始
        int temp = a[i];                                // temp 记录要调整的节点
        while(j<n){                                        //还有叶子节点怎循环
            if(j<n-1 && a[j]<a[j+1])                    //保证不越界，选择两子重的较大者
                j++;
            if(temp >= a[j])                            //根节点较大，停止调整
                break;
            a[(j-1)/2] = a[j];                            //子节点较大，本应该交换，但覆盖即可，temp保存着交换后该节点的信息
            j = j*2+1;                                    //继续检查子节点是否需要交互，如果越界则表明没有子节点
        }
        a[(j-1)/2] = temp;                                //最后停下来的位置上赋上原始节点的值
    }
        2 楼    cjf068    2012-02-19              LuckYes 写道楼主如果用最小堆的话，最好用调整堆的方式来构建堆，这样效率更高以及更容易理解。
 public static void Sort(int[] a){
        int temp;
        int n = a.length;
        Display(a); 
        
        for(int i = n/2-1;i>=0;i--)                        //从非叶子节点开始
            Adjust(a, i, n);
                                        //初始化堆
        for(int i = n-1;i > 0;i--){
            temp = a[0];                                //交换根节点与最后一个叶子节点，要调整的范围减1
            a[0] = a[i];
            a[i] = temp;  
            Adjust(a, 0, i);                           //不断减小长度、 交换、调整
        }    
        Display(a);
    } 
    
    public static void Adjust(int[] a, int i, int n){     //调整函数，参数含义 代表从哪个节点开始跳着，n代表堆的长度范围
        int j = 2*i+1;                                    //从要调整的节点的子节点开始
        int temp = a[i];                                // temp 记录要调整的节点
        while(j<n){                                        //还有叶子节点怎循环
            if(j<n-1 && a[j]<a[j+1])                    //保证不越界，选择两子重的较大者
                j++;
            if(temp >= a[j])                            //根节点较大，停止调整
                break;
            a[(j-1)/2] = a[j];                            //子节点较大，本应该交换，但覆盖即可，temp保存着交换后该节点的信息
            j = j*2+1;                                    //继续检查子节点是否需要交互，如果越界则表明没有子节点
        }
        a[(j-1)/2] = temp;                                //最后停下来的位置上赋上原始节点的值
    }
    
呵呵 谢谢提醒，其实应该用最大堆，每次和堆顶元素比较，发帖之后我想起来了，后来没改