从大量数据中取最小的前k个数

我就是我 2021-09-23 04:08 273阅读 0赞

**问题描述：**从大量整数中，取前k个最小的数  
**思路描述：**  
1.利用最大堆性质，根节点的数据最大。  
2.首先读取k个数据，构造大小为k+1的最大堆。（有效索引为1-k）  
3.每次读取一个数据，若该数比最大堆的第一个数据小，则将该数据最为最大堆的第一个数，然后执行Max\_Heapfy函数维护最大堆得性质。  
4.数据读取结束，该堆中的数据为最小的k个数  
5.对该堆进行排序，从小到大进行排序后输出。  
Java代码：  
1.随机生成1亿个数（待测试的数据，耗时有点长）

import java.io.File;
    import java.io.FileNotFoundException;
    import java.io.FileOutputStream;
    import java.io.PrintStream;
    import java.util.Random;
    
    public class GenNum { 
    
        public static void main(String[] args) throws FileNotFoundException {
            // TODO Auto-generated method stub
            FileOutputStream fs = new FileOutputStream(new File("D:\\test.txt"));
            PrintStream p = new PrintStream(fs);
            Random random=new Random();
            for(int i=0;i<100000000;i++){
                p.println(random.nextInt(100000000));
            }
            p.close();
            System.out.println("Over");
        }
    
    }

2.公共类（这里设置公共类Common.cs 因为本地代码是最小堆最大堆公用的）  
作用：打印堆数据、获取父节点、左右孩子节点

public class Common {
        //父节点
        public static int parent(int i) {
            return i/2;
        }
        //左节点
        public static int left(int i) {
            return 2*i;
        }
        //右节点
        public static int right(int i) {
            return 2*i+1;
        }
        // 打印数组
        public static void print(int[] A) {
            // TODO Auto-generated method stub
            for (int i = 1; i < A.length; i++) {
                System.out.print(A[i] + "\t");
            }
            System.out.println();
        }
    }

3.最大堆（包括构造最大堆、维持最大堆、和最大堆排序）

public class MaxHeap { 
        public static int[] arr;
        /** * 堆排序 * @param A */
        public static void HeapSort() {
            // TODO Auto-generated method stub
            Build_Max_Heap();
            int length=arr.length-1;
            //每次将根节点与需要排序的最后一个数交换 后维持最大堆
            for(int i=length; i>1;i--){         
                int temp = arr[i];
                arr[i]=arr[1];
                arr[1]=temp;
                Max_Heapfy(1,--length);     
            }
        }
        /** * 构建最大堆 * @param A */
        public static void Build_Max_Heap() {
            // TODO Auto-generated method stub
            int length=arr.length-1;
            for(int i=length/2;i>0;i--){
                Max_Heapfy(i, length);
            }
        }
    
        /** * 维持最大堆 * @param A * arrparam i 从第i个元素开始维护 * @param length 维持堆的数组长度 */
        public static void Max_Heapfy(int i,int length) {
            // TODO Auto-generated method stub
            int l=Common.left(i);
            int r=Common.right(i);
            int largest=0;
            if(l<=length && arr[l]>arr[i]){
                largest=l;
            }else{
                largest=i;
            }
            if(r<=length && arr[r]>arr[largest]){
                largest=r;
            }
            if(largest!=i){
                int temp = arr[i];
                arr[i]=arr[largest];
                arr[largest]=temp;
                Max_Heapfy(largest,length);
            }       
    
        }
    }

4.测试  
输入为:1.文本文件 共1亿条数据 2.k

import java.io.BufferedReader;
    import java.io.File;
    import java.io.FileReader;
    import java.io.IOException;
    import java.util.Scanner;
    
    public class test { 
    
        public static void main(String[] args) throws IOException {
            // TODO Auto-generated method stub
            Scanner scanner = new Scanner(System.in);
            System.out.println("请输入k");
            int k = scanner.nextInt();
            long l = System.currentTimeMillis();
            // 先读取k个数 构建最大堆
            // 依次读取数据，如果改数比根节点大，则替换根节点的数据，然后维持最大堆的性质
            MaxHeap heap = new MaxHeap();
            heap.arr = new int[k+1];
            // 读取文件
            File file = new File("D:\\test.txt");// Text文件
            BufferedReader br = new BufferedReader(new FileReader(file));// 构造一个BufferedReader类来读取文件
    
            String s = null;    
            int i=1;
            while ((s = br.readLine()) != null&&i<=k) {
       // 使用readLine方法，一次读一行
                //System.out.println(s);
                heap.arr[i++]=Integer.parseInt(s);
            }
            heap.Build_Max_Heap();
            int temp;
            while ((s = br.readLine()) != null) {
       // 使用readLine方法，一次读一行
                //System.out.println(s);
                temp = Integer.parseInt(s);
                if(temp<heap.arr[1]){
                    heap.arr[1]=temp;
                    heap.Max_Heapfy(1, heap.arr.length-1);
                }
            }
            heap.HeapSort();
            Common.print(heap.arr);
            br.close();
            ;
            System.out.println("耗时" + (System.currentTimeMillis() - l) + "毫秒");
    
        }
    
    }

结论：1亿条数据取最小的10个数字，耗时14秒，耗时很长，求大神给出优化意见。