java 使用二叉堆实现 TopK 算法

首先 本小白是参考这里写链接内容 和这里写链接内容
两位 博主的文章

1.首先，什么是二叉堆，*上是这么描述的：
当父节点的键值总是大于或等于任何一个子节点的键值时为最大堆。 当父节点的键值总是小于或等于任何一个子节点的键值时为最小堆。

2.二叉堆一般用数组来表示。如果根节点在数组中的位置是1，第n个位置的子节点分别在2n和 2n+1。因此，第1个位置的子节点在2和3，第2个位置的子节点在4和5。以此类推。这种基于1的数组存储方式便于寻找父节点和子节点。
如果存储数组的下标基于0，那么下标为i的节点的子节点是2i + 1与2i + 2；其父节点的下标是⌊(i − 1) ∕ 2⌋。

3.如果要向二叉堆中新添一个数的话,如下图：

图片来源这里写链接内容

利用二叉堆算法来实现 TopN
实现流程是：
1、先读取10个或100个数到数组里面，这就是我们的topN数.

2、调用生成小顶堆函数，把这个数组生成一个小顶堆结构，这个时候堆顶一定是最小的.
    2.1、按照图一的规则，把数组的值按照二叉堆的索引位置放好。
    2.2、从最后一个有子节点的索引位置开始，如果其子节点的最小值比父节点的值小，那就交换子父节点的值；（其实就是把数组的两个值交换而已）
        2.2.1、 如果其子节点还有子节点，就递归调用，把最小数往上顶。
    2.3、再找倒数第二个有子节点的索引，再比较，再交换值。

3、从文件或者数组依次遍历剩余的所有数.

4、每遍历出来一个则跟堆顶的元素进行大小比较，如果小于堆顶元素则抛弃，如果大于堆顶元素则替换之.

5、跟堆顶元素替换完毕之后，在调用生成小顶堆函数继续生成小顶堆，因为需要再找出来一个最小的.
    5.1、 其实，在选出的前10个数，猜想默认这个数组存的就是最大的10个数，如果在剩余的数里面有比这10个数的最小数还大的，那就果断放进来，把那个二叉堆的最小数抛出，然后再找。。。

6、重复以上4~5步骤，这样当全部遍历完毕之后，我们这个小顶堆里面的就是最大的topN，因为我们的小顶堆永远都是排除最小的留下最大的，而且这个调整小顶堆速度也很快，只是相对调整下，只要保证根节点小于左右节点就可以.

7、算法复杂度的话按top10最坏的情况下，就是每遍历一个数，如果跟堆顶进行替换，需要调整10次的情况，也要比排序速度快，而且也不是把所有的内容全部读入内存，可以理解成就是一次线性遍历.

理论讲完了，下面就是代码：

 private List<Integer> arrayList;
     //生成小顶堆函数
    void head(int[] arr, int idx){
        int left = (idx << 1)+1;
        int right = (idx << 1)+2;
        int min,temp;
        if (left>=arr.length){
            return;
        }
        if ((right<arr.length)&&arr[right]<arr[left]){
            min = right;
        }else{
            min = left;
        }
        if (arr[idx]>arr[min]){
            temp = arr[idx];
            arr[idx] = arr[min];
            arr[min] = temp;
            head(arr,min);
        }
    }

 @org.junit.Test
        public  void  testTopkMethod(){
            long startTime=System.currentTimeMillis();   //获取开始时间

           this.arrayList = new ArrayList<Integer>();
           for (Integer i = 0;i<5000000;i++){
                arrayList.add(i);
           }
       //打乱顺序
          Collections.shuffle(arrayList);
          int[] numArray = new  int[arrayList.size()];
          for (int i = 0;i<arrayList.size();i++){
              numArray[i] = arrayList.get(i);
          }

          //先取出10个到数组
          List<Integer>topList = arrayList.subList(0,10);
          System.out.println(topList);

          //获取最后一个有子节点的索引位置
          //因为在构造小顶堆的时候是从最后一个有左或右节点的位置
          //开始从下往上不断的进行移动构造（具体可看上面的图去理解）
          int idx = topList.size()/2 - 1;
          //生成小顶堆
          int[] arr = new  int[topList.size()];
          for (int i =0;i<topList.size();i++){
              arr[i] = topList.get(i);
          }
          for (int i = idx;i>=0;i--){
              head(arr,i);
          }
          //这里可以看到，就是开始遍历剩下的所有元素
          for (int i = arr.length;i<numArray.length;i++){
              //每遍历一个则跟堆顶元素进行比较大小
              if (numArray[i]>arr[0]){
                  arr[0] = numArray[i];
                   /*
                      重新调用生成小顶堆函数进行维护，只不过这次是从堆顶
                      的索引位置开始自上往下进行维护，因为我们只是把堆顶
                      的元素给替换掉了而其余的还是按照根节点小于左右节点
                      的顺序摆放这也就是我们上面说的，只是相对调整下，并
                      不是全部调整一遍
                    */
                   head(arr,0);
              }
          }
            long endTime=System.currentTimeMillis(); //获取结束时间
            System.out.println("程序运行时间： "+(endTime-startTime)+"ms");
            for (int i =0;i<arr.length;i++){
              System.out.println(arr[i]);
          }
     }

感谢这里写链接内容
简单方式博主，很受启发。（我这耗时2.7s，php耗时1.4s,看起来我这代码还是有些问题）