Java最小堆解决TopK问题
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，直到源数据遍历结束。
最小堆的实现：
public class TopK{public static void main(String[] args){// 源数据int[] data = {56,275,12,6,45,478,41,1236,456,12,546,45};// 获取Top5int[] top5 = topK(data, 5);for(int i=0;i<5;i++){System.out.println(top5[i]);}}// 从data数组中获取最大的k个数private static int[] topK(int[] data,int k){// 先取K个元素放入一个数组topk中int[] topk = new int[k]; for(int i = 0;i< k;i++){topk[i] = data[i];}// 转换成最小堆MinHeap heap = new MinHeap(topk);// 从k开始，遍历datafor(int i= k;i<data.length;i++){int root = heap.getRoot();// 当数据大于堆中最小的数（根节点）时，替换堆中的根节点，再转换成堆if(data[i] > root){heap.setRoot(data[i]);}}return topk;}}作者：叉叉哥 转载请注明出处：http://blog.csdn.net/xiao__gui/article/details/8687982