海量数据topK算法

    背景：由于内存限制，长度为一亿的某类型的数组无法全部放入内存进行排序，进而无法取出前100的元素,多见于搜索排名，更恶劣的情况是这一亿条数据还分布在多台机器上

    原理与简化：遍历长度为N的数组的前K个元素构建小顶堆，对于剩余的N-K的元素：小于其根节点的过滤掉，大于根节点则替换之并heapify该小顶堆，时间复杂度近似为N*O(logK)，因此只要实现一个定制版的heapify函数即可！

    关键代码如下：

/**
     * 小顶堆欢迎新同学
     * @param arr 某数组，不考虑根节点，构成一小顶堆，length为K
     * @param startIndex 被替换后的根节点,应为0
     */
    public void heapify4topK(int[] arr,int startIndex){
        int n=arr.length;
        int startValue=arr[startIndex];//要沉下去的数
        int leftSon=2*startIndex+1;
        int minIndex=0;
        while (leftSon
            if (leftSon==n-1||arr[leftSon]<=arr[leftSon+1]){
                minIndex=leftSon;
            }else if(arr[leftSon]>arr[leftSon+1]){
                minIndex=leftSon+1;
            }
            int minSon = arr[minIndex];
            if(minSon>=startValue){
                break;
            }
            arr[startIndex]=minSon;
            startIndex=minIndex;
            leftSon=2*startIndex+1;
        }
        arr[startIndex]=startValue;
    }