使用最小堆解决海量数据数据中求TopK最大的几个数问题

迈不过友情╰ 2022-02-28 03:56 248阅读 0赞

前几天面试遇到了这么一个问题:

### 求一亿个数据中最大的100个数. ###

这个问题一脸懵逼我.  
后来查了资料说使用HASH函数以及分治的思想来解决.将这1亿个数根据HASH去重然后根据hash值分别存储到1000个分区内,然后每个分区都使用一个容量为100的最小堆得到每个区最大的100个数.  
最后将1000个分区内得到的最小堆再合并处理即可.

这里主要是最小堆的问题.  
怪我基础差,面试过后又补了补最小堆的知识.参考网上,写了一个最小堆的Demo来巩固知识.

有些概念得知道,一般最小堆都是使用数组来存储的.  
如果一个子节点下标位置为x,那么他的父类位置即为(x-1)/2  
如果一个父节点下标位置为y,那么他的右节点位置为(x+1)<<1,左节点位置为(x+1)<<1.  
`注意:`  
(数组长度)/2-1代表下标最大的那个有子节点的父节点位置.  
因为最后一个节点位置为(数组长度-1),然后其父类节点位置为(数组长度-2)/2,即为(数组长度)/2-1

//最小堆
    class MinHeap{
    	//最小堆维持的大小
        private int[] data;
        public MinHeap(int[] data){
            this.data = data;
            buildHeap();
        }
        //建立最小堆
        private void buildHeap(){
            for(int i=(data.length)/2-1;i>=0;i--){
                heapify(i);
            }
        }
        private void heapify(int i){
            int left = left(i);
            int right = right(i);
            int small = i;
            if(left<data.length&&data[left]<data[small]){
                small = left;
            }
            if(right<data.length&&data[right]<data[small]){
                small = right;
            }
            if(i == small){
                return;
            }
            swap(i,small);
            heapify(small);
        }
        private void swap(int i, int j){
            int temp = data[i];
            data[i] = data[j];
            data[j] =temp;
        }
        private int left(int i){
            return ((i+1)<<1)-1;
        }
        private int right(int i){
            return (i+1)<<1;
        }
        public int getRoot(){
            return data[0];
        }
        public void setRoot(int root){
            data[0] = root;
            heapify(0);
        }
    }
    public class Main {
    
        public static void main(String[] args) {
           int[] number = new int[]{4,5,1,9,9,1,2,3,12};
           int[] top7 = topK(number,7);
           for(int i=0;i<top7.length;i++){
               System.out.print(top7[i]+" ");
           }
    
        }
        private static int[] topK(int[] number,int k) {
            int[] top7 = new int[k];
            for (int i = 0; i < k; i++) {
                top7[i] = number[i];
            }
            MinHeap minHeap = new MinHeap(top7);
            for(int i = k;i<number.length;i++){
                int root = minHeap.getRoot();
                if(number[i]<=root){
                    break;
                }else{
                    minHeap.setRoot(number[i]);
                }
            }
            return top7;
        }
    }