使用小顶堆解决TOPK问题

待我称王封你为后i 2022-11-16 05:47 163阅读 0赞

## 首先我们需要构建一个小顶堆 ##

我们可以用PriorityQueue这个优先队列,它给我们从小到大排序好了的,至于什么是小顶堆可以去看看堆和数的概念.

> PriorityQueue pq = new PriorityQueue<>();

## 我们需要对小顶堆的堆顶与插入的数进行比较 ##

private int k = 1000;  //从文件中找到最大的一千个数
        PriorityQueue<Integer> pq = new PriorityQueue<>(k);
        public void seclet(int num){
        
            if (pq.size() < k){
          //往堆中添加文件的前面一千个数
                pq.add(num);
            }else if (pq.peek() < num){
          //如果堆顶小于文件中传递的数
                pq.poll();    //删除堆顶
                pq.add(num);   //将新数添加堆中,PriorityQueue会自动排序构成小顶堆
            }
        }

## 获取文件中的数,并进行判断 ##

public void run(){
        
            try {
        
                BufferedReader br = new BufferedReader(new FileReader("jm.txt"));
                String len;
                while ((len = br.readLine())!=null){
        
                    seclet(Integer.parseInt(len));
                    if (pq.peek() == 9999){
           //这个if判断看情况,这里我已知小顶堆中一千个最大的都是9999,为了效率问题,如果没有要求可以不用写
                        break;
                    }
                }
                BufferedWriter bw = new BufferedWriter(new FileWriter("n.txt"));
                for (int i = 0; i < k && !pq.isEmpty(); i++) {
        
                    bw.write(pq.poll().toString());   //将文字以字符串的格式传进文件,否则会乱码
                    bw.write("\n");
                }
                br.close();
                bw.close();
            } catch (Exception e) {
        
                e.printStackTrace();
            }
        }

## 最后看看从1024*1024*128个随机数中取出1000个最大的数并写入文件中一共花费多少时间 ##

public static void main(String[] args) {
        
            long start = System.currentTimeMillis();
            T2 t2 = new T2();
            t2.run();
            System.out.println(System.currentTimeMillis()-start + "ms");
        }

> 运行结果:  
> ![在这里插入图片描述][20210406162736869.png]
> 
> 可以看出来是非常快速的  
> 怎么生成一亿个随机数快速的写入文件中可以看看前面的一篇文章  
> 有什么问题我非常乐意帮忙解决,因为我也是小白,想要磨炼磨炼

[20210406162736869.png]: /images/20221022/426f67f469514def9561c76079e3f1ed.png