Java最小堆解决TopK问题

标签： java topk 问题 | 发表时间：2017-01-19 01:56 | 作者：
出处：http://www.iteye.com

www.toutiao.im

其实我们与大数据并不遥远，比如要从海量数据中按大小或频率挑出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，直到源数据遍历结束。

 

 

最小堆的实现：

[java]  view plain  copy
  1. public class MinHeap  
  2. {  
  3.     // 堆的存储结构 - 数组  
  4.     private int[] data;  
  5.       
  6.     // 将一个数组传入构造方法，并转换成一个小根堆  
  7.     public MinHeap(int[] data)  
  8.     {  
  9.         this.data = data;  
  10.         buildHeap();  
  11.     }  
  12.       
  13.     // 将数组转换成最小堆  
  14.     private void buildHeap()  
  15.     {  
  16.         // 完全二叉树只有数组下标小于或等于 (data.length) / 2 - 1 的元素有孩子结点，遍历这些结点。  
  17.         // *比如上面的图中，数组有10个元素， (data.length) / 2 - 1的值为4，a[4]有孩子结点，但a[5]没有*  
  18.         for (int i = (data.length) / 2 - 1; i >= 0; i--)   
  19.         {  
  20.             // 对有孩子结点的元素heapify  
  21.             heapify(i);  
  22.         }  
  23.     }  
  24.       
  25.     private void heapify(int i)  
  26.     {  
  27.         // 获取左右结点的数组下标  
  28.         int l = left(i);    
  29.         int r = right(i);  
  30.           
  31.         // 这是一个临时变量，表示 跟结点、左结点、右结点中最小的值的结点的下标  
  32.         int smallest = i;  
  33.           
  34.         // 存在左结点，且左结点的值小于根结点的值  
  35.         if (l < data.length && data[l] < data[i])    
  36.             smallest = l;    
  37.           
  38.         // 存在右结点，且右结点的值小于以上比较的较小值  
  39.         if (r < data.length && data[r] < data[smallest])    
  40.             smallest = r;    
  41.           
  42.         // 左右结点的值都大于根节点，直接return，不做任何操作  
  43.         if (i == smallest)    
  44.             return;    
  45.           
  46.         // 交换根节点和左右结点中最小的那个值，把根节点的值替换下去  
  47.         swap(i, smallest);  
  48.           
  49.         // 由于替换后左右子树会被影响，所以要对受影响的子树再进行heapify  
  50.         heapify(smallest);  
  51.     }  
  52.       
  53.     // 获取右结点的数组下标  
  54.     private int right(int i)  
  55.     {    
  56.         return (i + 1) << 1;    
  57.     }     
  58.   
  59.     // 获取左结点的数组下标  
  60.     private int left(int i)   
  61.     {    
  62.         return ((i + 1) << 1) - 1;    
  63.     }  
  64.       
  65.     // 交换元素位置  
  66.     private void swap(int i, int j)   
  67.     {    
  68.         int tmp = data[i];    
  69.         data[i] = data[j];    
  70.         data[j] = tmp;    
  71.     }  
  72.       
  73.     // 获取对中的最小的元素，根元素  
  74.     public int getRoot()  
  75.     {  
  76.             return data[0];  
  77.     }  
  78.   
  79.     // 替换根元素，并重新heapify  
  80.     public void setRoot(int root)  
  81.     {  
  82.         data[0] = root;  
  83.         heapify(0);  
  84.     }  
  85. }  

 

利用最小堆获取TopK：

[java]  view plain  copy
  1. public class TopK  
  2. {  
  3.     public static void main(String[] args)  
  4.     {  
  5.         // 源数据  
  6.         int[] data = {56,275,12,6,45,478,41,1236,456,12,546,45};  
  7.           
  8. // 获取Top5  
  9.         int[] top5 = topK(data, 5);  
  10.           
  11.         for(int i=0;i<5;i++)  
  12.         {  
  13.             System.out.println(top5[i]);  
  14.         }  
  15.     }  
  16.       
  17.     // 从data数组中获取最大的k个数  
  18.     private static int[] topK(int[] data,int k)  
  19.     {  
  20.         // 先取K个元素放入一个数组topk中  
  21.         int[] topk = new int[k];   
  22.         for(int i = 0;i< k;i++)  
  23.         {  
  24.             topk[i] = data[i];  
  25.         }  
  26.           
  27.         // 转换成最小堆  
  28.         MinHeap heap = new MinHeap(topk);  
  29.           
  30.         // 从k开始，遍历data  
  31.         for(int i= k;i<data.length;i++)  
  32.         {  
  33.             int root = heap.getRoot();  
  34.               
  35.             // 当数据大于堆中最小的数（根节点）时，替换堆中的根节点，再转换成堆  
  36.             if(data[i] > root)  
  37.             {  
  38.                 heap.setRoot(data[i]);  
  39.             }  
  40.         }  
  41.           
  42.         return topk;  
  43. }  
  44. }  

介绍完了最小堆，顾名思义，相应的还有最大堆。

www.toutiao.im

 



已有 0 人发表留言，猛击->> 这里<<-参与讨论


ITeye推荐



相关 [java topk 问题] 推荐：

Java最小堆解决TopK问题

- - ITeye博客
其实我们与大数据并不遥远，比如要从海量数据中按大小或频率挑出top k，假定机器是多核的内存有限的，我们采用多线程分块处理数据，最后合并处理. 那么，处理每一块数据的top k(i)可以采用哪些算法呢. TopK问题是指从大量数据（源数据）中获取最大（或最小）的K个数据. TopK问题是个很常见的问题：例如学校要从全校学生中找到成绩最高的500名学生，再例如某搜索引擎要统计每天的100条搜索次数最多的关键词.

飘逸的python - 大数据TopK问题的quick select解法

- - CSDN博客推荐文章
TopK问题,即寻找最大的K个数,这个问题非常常见,比如从1千万搜索记录中找出最热门的10个关键词.. 先排序,然后截取前k个数.. 时间复杂度：O(n*logn)+O(k)=O(n*logn). 维护容量为k的最小堆.根据最小堆性质,堆顶一定是最小的,如果小于堆顶,则直接pass,如果大于堆顶,则替换掉堆顶,并heapify整理堆,其中heapify的时间复杂度是logk..

Java写xml文件的编码问题

- - CSDN博客推荐文章
最近项目中需要生成xml格式的配置文件，用的是 javax.xml.transform.Transformer 类中提供的transform方法，在本地执行没问题，但是一旦把工程部署到Tomcat下运行，就会出现中文乱码的现象，纠结了许久，在大神的帮助下终于解决了. 有篇文章其实已经讲的很清楚了，链接如下：.

Java String 的十大常见问题

- - ITeye博客
Java字符串经常被问到的排名前十的问题. 　 　1、如何比较字符串. 使用 “==”  还是 “equals()”. 　　简单来讲，“==”比较的是引用（对象的内存地址），“equals()” 比较值是否相等. 除非你想检测两个字符串是否是同一对象，否则都用equals(). 　　当然了解字符串池的概念更好.

java socket 长连接read阻塞问题

- - PHP & Java
1 约定发送的数据长度，比如 http的 keepAlive 就是必须依赖这个的 Content-Length. 2 设置超时的时间，根据我的经验，只有在Socket级别设置才有效. socket.setSoTimeout(100); // 如果超过100毫秒还没有数据，则抛出 SocketTimeoutException.

15个易遗忘的Java问题

- - ITeye博客
1.Java中的基本数据类型以及所占内存大小. short    2字节. float    4字节. double    8字节. char    2字节(Unicode-16).     布尔类型boolean比较特殊，尽管Java虚拟机定义了boolean类型，但虚拟机对boolean类型的支持是有限的，没有为boolean值单独设计JVM指令.

Java静态代码块的问题

- - ITeye博客
在查看别人代码的时候 看到了 static静态代码块  之后经过搜索和自己的亲试，下面贴出测试代码和解释. System.out.println("父类--静态代码块");. System.out.println("父类--构造方法");. System.out.println("父类--非静态代码块");.

Java通过mysql-connector-java-8.0.11连接MySQL Server 8.0遇到的几个问题

- - 编程语言 - ITeye博客
这次新安装了一个MySQL数据库，然后navicat连接数据库一点问题没有. 但是通过Java的jdbc连接却怎么都建立不了连接. 网上找了很久找到了原因：. 数据库用的是Mysql8版本，但工程里面mysql驱动包却是5.1.37版本. 只需修改驱动包为8.0.11版本即可. 而且驱动的包也改变了，由原来的：/generatorSqlmapCustom/lib/mysql-connector-java-5.1.28-bin.jar.

记录帖：碰到的一些Java问题

- gengmao - BlueDavy之技术blog
这个贴用于记录自己碰到过的一些Java问题，会根据经验不断增加，以便总结，:). Case: 某应用出现启动后集群中部分node成功，部分node失败. 1、失败的node抛出的是NoClassDefFoundError，这些node在环境上和应用包上是完全一致的，因此猜想是classloader装载class时出现了什么问题；.

深入分析 Java 中的中文编码问题

- Alex - IBM developerWorks 中国 : 文档库
编码问题一直困扰着开发人员，尤其在 Java 中更加明显，因为 Java 是跨平台语言，不同平台之间编码之间的切换较多. 本文将向你详细介绍 Java 中编码问题出现的根本原因，你将了解到：Java 中经常遇到的几种编码格式的区别；Java 中经常需要编码的场景；出现中文问题的原因分析；在开发 Java web 程序时可能会存在编码的几个地方，一个 HTTP 请求怎么控制编码格式.