算法-大数据量获取TopK的几种方案

import java.util.Arrays;/*** 通过堆这种数据结构* 获得大数据量中的TopK*/public class TopKStack {    public static void main(String[] args) {        //定义一个数组，找出该数组中的topK，大数据量不好搞到，先用这个数组测试        int [] datas = {2,3,42,1,34,5,6,67,3,243,8,246,123,6,32,3451,23,5,6,31,5,6,2346,36};        int [] re = getTopK(datas,10);        System.out.println(Arrays.toString(re));    }    /**    * 获取前topk的方法    * @param datas 原数组    * @param num 前topNum    * @return 最后的topNum的堆数组    */    static int[] getTopK(int[] datas,int num){        //定义存储前num个元素的数组，用于建堆        int[] res = new int[num];        //初始化数组        for (int i = 0; i < num; i++) {            res[i] = datas[i];        }        //建造初始化堆        for (int i = (num - 1)/2; i >= 0 ; i--) {            shift(res,i);        }        //遍历查找num个最大值        for (int i = num; i < datas.length; i++) {            if (datas[i] > res[0]){                res[0] = datas[i];                shift(res,0);            }        }        return res;    }    /**    * 调整元素满足堆结构    * @param datas    * @param index    * @return    */    static int[] shift(int[] datas ,int index){        while(true){            int left = (index<<1) + 1; //左孩子            int right = (index<<1) + 2; //右孩子            int min_num = index; //标识自身节点和孩子节点中最小值的位置            //判断是否存在左右孩子，并且得到左右孩子和自身的最小值            if (left <= datas.length-1&&datas[left] < datas[index]){                min_num = left;            }            if (right <= datas.length-1&&datas[right] < datas[min_num]){                min_num = right;        }        //如果最小值不等于自身，则将最小值与自身交换        if (min_num != index){            int temp = datas[index];            datas[index] = datas[min_num];            datas[min_num] = temp;        }else{            //此处break是因为我们是从树的最下面进行调整的，如果上层节点符合堆，则下层节点一定符合！            break;        }        //执行到此处，说明可能需要调整下面的节点，则将初始节点赋值为最小值所在的节点位置，        // 因为最大值点的位置进行了交换，可能下层节点就不满足堆性质        index = min_num;    }    return datas;   }}