Java最小堆解决TopK问题

其实我们与大数据并不遥远，比如要从海量数据中按大小或频率挑出top k，假定机器是多核的内存有限的，我们采用多线程分块处理数据，最后合并处理。那么，处理每一块数据的top k(i)可以采用哪些算法呢？

 

TopK问题是指从大量数据（源数据）中获取最大（或最小）的K个数据。

TopK问题是个很常见的问题：例如学校要从全校学生中找到成绩最高的500名学生，再例如某搜索引擎要统计每天的100条搜索次数最多的关键词。

 

对于这个问题，解决方法有很多：

 

方法一：对源数据中所有数据进行排序，取出前K个数据，就是TopK。

但是当数据量很大时，只需要k个最大的数，整体排序很耗时，效率不高。

方法二：维护一个K长度的数组a[]，先读取源数据中的前K个放入数组，对该数组进行升序排序，再依次读取源数据第K个以后的数据，和数组中最小的元素（a[0]）比较，如果小于a[0]直接pass，大于的话，就丢弃最小的元素a[0]，利用二分法找到其位置，然后该位置前的数组元素整体向前移位，直到源数据读取结束。

这比方法一效率会有很大的提高，但是当K的值较大的时候，长度为K的数据整体移位，也是非常耗时的。

 

对于这种问题，效率比较高的解决方法是使用最小堆。

 

最小堆（小根堆）是一种数据结构，它首先是一颗完全二叉树，并且，它所有父节点的值小于或等于两个子节点的值。

最小堆的存储结构（物理结构）实际上是一个数组。如下图：

 

 

堆有几个重要操作：

BuildHeap：将普通数组转换成堆，转换完成后，数组就符合堆的特性：所有父节点的值小于或等于两个子节点的值。

Heapify(int i)：当元素i的左右子树都是小根堆时，通过Heapify让i元素下降到适当的位置，以符合堆的性质。

 

回到上面的取TopK问题上，用最小堆的解决方法就是：先取源数据中的K个元素放到一个长度为K的数组中去，再把数组转换成最小堆。再依次取源数据中的K个之后的数据和堆的根节点（数组的第一个元素）比较，根据最小堆的性质，根节点一定是堆中最小的元素，如果小于它，则直接pass，大于的话，就替换掉跟元素，并对根元素进行Heapify，直到源数据遍历结束。

 

 

最小堆的实现：

    {           // 完全二叉树只有数组下标小于或等于 (data.length) / 2 - 1 的元素有孩子结点，遍历这些结点。           // *比如上面的图中，数组有10个元素， (data.length) / 2 - 1的值为4，a[4]有孩子结点，但a[5]没有*           for (int i = (data.length) / 2 - 1; i  = 0; i--)            {               // 对有孩子结点的元素heapify               heapify(i);           }       }              private void heapify(int i)       {           // 获取左右结点的数组下标           int l = left(i);             int r = right(i);                      // 这是一个临时变量，表示 跟结点、左结点、右结点中最小的值的结点的下标           int smallest = i;                      // 存在左结点，且左结点的值小于根结点的值           if (l   data.length   data[l]   data[i])                 smallest = l;                        // 存在右结点，且右结点的值小于以上比较的较小值           if (r   data.length   data[r]   data[smallest])                 smallest = r;                        // 左右结点的值都大于根节点，直接return，不做任何操作           if (i == smallest)                 return;                        // 交换根节点和左右结点中最小的那个值，把根节点的值替换下去           swap(i, smallest);                      // 由于替换后左右子树会被影响，所以要对受影响的子树再进行heapify           heapify(smallest);       }              // 获取右结点的数组下标       private int right(int i)       {             return (i + 1)   1;         }          // 获取左结点的数组下标       private int left(int i)        {             return ((i + 1)   1) - 1;         }              // 交换元素位置       private void swap(int i, int j)        {             int tmp = data[i];             data[i] = data[j];             data[j] = tmp;         }              // 获取对中的最小的元素，根元素       public int getRoot()       {               return data[0];       }       // 替换根元素，并重新heapify       public void setRoot(int root)       {           data[0] = root;           heapify(0);       }  
                           // 当数据大于堆中最小的数（根节点）时，替换堆中的根节点，再转换成堆               if(data[i]   root)               {                   heap.setRoot(data[i]);               }           }                      return topk;  

 

系统可用内存10M，从一个2G的文本文件里统计出现次数排名前10的单词，用MapReduce再合适不过，分而治之。

原文链接:[http://wely.iteye.com/blog/2353982]

《徐徐道来话Java》：PriorityQueue和最小堆 在讲解PriorityQueue之前，需要先熟悉一个有序数据结构：最小堆。 最小堆是一种经过排序的完全二叉树，其中任一非终端节点数值均不大于其左孩子和右孩子节点的值。 可以得出结论，如果一棵二叉树满足最小堆的要求，那么，堆顶（根节点）也就是整个序列的最小元素。
Java实现图书管理系统 本篇文章是对目前Java专栏已有内容的一个总结练习，希望各位小主们在学习完面向对象的知识后，可以阅览本篇文章后，自己也动手实现一个这样的demo来加深总结应用已经学到知识并进行巩固。
Java实现拼图小游戏（1）—— JFrame的认识及界面搭建 如果要在某一个界面里面添加功能的话，都在一个类中，会显得代码难以阅读，而且修改起来也会很困难，所以我们将游戏主界面、登录界面、以及注册界面都单独编成一个类，每一个类都继承JFrame父类，并且在类中创建方法来来实现页面
Java实现拼图小游戏（7）—— 计步功能及菜单业务的实现 注意由于我们计步功能的步数要在重写方法中用到，所以不能将初始化语句写在方法体内，而是要写在成员位置。在其名字的时候也要做到“见名知意”，所以我们给它起名字为step
Java实现拼图小游戏（7）—— 作弊码和判断胜利 当我们好不容易把拼图复原了，但是一点提示也没有，完全看不出来是成功了，那么我们就需要有判断胜利的功能去弹出“成功”类的图片，以便于玩家选择是重新开始还是退出小游戏