寻找最大的K个数，如果所有的数据全部可以放入内存，就可以使用random select算法在线性时间内寻找第K大的数，再得到最大的K个数。

参考：http://www.cnblogs.com/luxiaoxun/archive/2012/08/06/2624799.html

如果不能把所有数据的数据都一次性放入内存，就可以维护一个大小为K的堆，找最大的K个数，就维护一个小根堆，堆顶元素为这最大的K个数中的最小元素。具体实现参考下面两个例子：

2亿个整数中求最大的100万之和

题目：有一个文件中保存了2亿个整数，每个整数都以' '分隔。求最大的100万个整数之和。

算法：
1. 首先建立一个容量为100万（Top K）的int数组，从文件读取整数填充。
2. 利用堆维护该100万条记录（确保堆顶元素为最小值）
3. 从文件中读取一个整数与堆顶元素比较，如果大于堆顶元素则替换该元素，并调整堆的结构。
4. 重复步骤3一直到数据读取完
5. 将数组中的元素全部相加，得到结果

参考代码：

View Code

测试数据：生成1000万个不重复的随机数

View Code

1000万个数据太大，打开文件很慢，可能会看不到，可以测试1万个数据中找最大的10个。

搜索引擎热门查询统计

题目描述：
搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。
假设目前有一千万个记录，这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。请你统计最热门的10个查询串，要求使用的内存不能超过1G。

解决方法：hash表+堆，去重复后不超过300万个，总大小不超过300万*255B=765MB，内存使用不超过1G。

第一步：先对这批海量数据预处理，在O(N)的时间内用Hash表完成去重复操作。
第二步：借助堆这个数据结构，找出Top K，时间复杂度为NlogK。即借助堆结构，可以在log量级的时间内查找和调整/移动。因此，维护一个K（该题目中是10）大小的小根堆（Kmin设为堆顶元素），然后遍历300万的Query，分别和Kmin进行对比比较（若X>Kmin，则更新并调整堆，否则，不更新），最终的时间复杂度是：O（N）+ N'*O（logK），（N为1000万，N’为300万）。

为了降低实现上的难度，假设这些记录全部是一些英文单词，即用户在搜索框里敲入一个英文单词，然后查询搜索结果，最后，要你统计输入单词中频率最大的前K个单词。复杂问题简单化了之后，编写代码实现也相对轻松多了，如下：

View Code

参考：http://blog.csdn.net/v_JULY_v/archive/2011/05/08/6403777.aspx

    本文转自阿凡卢博客园博客，原文链接：http://www.cnblogs.com/luxiaoxun/archive/2012/09/11/2679743.html，如需转载请自行联系原作者