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

求一亿个数据中最大的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;
    }
}