Top K的问题：

给出大量数据，找出其中前K个最大（小）的数，或者在海量数据中找到出现频率最好的前K个数。

一、给出大量数据（N个），找出其中前K个最大数（没有其他资源上的限制）

 1、使用排序算法

　　直接使用排序算法，如快速排序，然后遍历找到最大的K个数。时间复杂度为O(NlogN)；

2、部分排序

　　因为，只要求出前K个最大值，所以我们不必全部排好。思路是：随意选出K个数形成一个数组，然后按从大到小进行排序，再从剩下的数中，选取一个数和数组中的最小值进行比较，若小于最小值，则取下一个数继续比较；若大于，则遍历数组找到相应的位置，淘汰掉数组中的最小值。反复操作直到遍历完所有数。这里更新一个数，会导致数组中后面数的移动，也增加了时间复杂度。时间复杂度为O（N*K）

3、堆排序

　　思想和方法2类似，思路如下：

　（1）可任取K个数，形成最小堆；时间复杂度为O(KlogK)。

　（2）从剩下的数中，选出一个数和最小堆的堆顶元素比较，若大于堆顶元素，则说明此时该数为最大的K个数中的一个，若小于则比较下一个数；

　（3）调整最小堆。时间复杂度为O(logK)，K为常数；

　（4）重复（2）~（3），直到所有数都完成。时间复杂度为O(NlogK)。

　3.1最小堆（动态示意图）实现代码如下：

 1 /*调整堆*/
 2 void minHeapFy(int *heap, int i, int heapSize)
 3 {
 4     int parent = i;
 5     int lChild = 2 * i + 1;
 6     int rChild = 2 * i + 2;
 7     int index = lChild;
 8     while (rChild<heapSize)
 9     {
10         if (rChild<heapSize&&heap[lChild]>heap[rChild])
11             index++;
12         if (heap[parent]<heap[index])
13             return;
14         else
15         {
16             swap(heap[parent], heap[index]);
17             parent = index;
18             lChild = 2 * parent + 1;
19             rChild = lChild + 1;
20             index = lChild;
21         }
22     }
23 }
24 
25 /*建最小堆*/
26 void buildHeap(int *heap, int n)
27 {
28     for (int i = n / 2-1 ; i >= 0; i--)
29     {
30         minHeapFy(heap, i, n);
31     }
32 }
33 
34 /*n为Top_K 的值,N为海量数据数*/
35 void minHeapSort(int *heap, int n, int *arr)
36 {
37     int N=30;                        //海量数据初始值
38     buildHeap(heap, n);          //先用n个元素建好堆
39     
40     for (int i = n; i<N;++i)
41     {
42         if (arr[i]>heap[0])
43         {
44             heap[0] = arr[i];
45             minHeapFy(heap, 0, n);
46         }
47     }
48 }

  整个问题的完全代码见这里。

二、统计最热门查询，首先就是要统计每个Query出现的次数，然后根据统计结果，找出Top K

　　问题描述（题目来源v_JULY_v）

 　　百度面试题：

　　搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。

　　假设目前有一千万个记录（这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。），请你统计最热门的10个查询串，要求使用的内存不能超过1G。

　　解决步骤：

1、Query统计

　　因为题中有提到重复度比较高，所以可以维护一个key为Query的字符串，value是Query出现次数的哈希表，每次读取一个Query，如果该字符串不在哈希表中，那么加入该字符串，并将value值设为1；如果在对应字符串的计数加1即可。时间复杂度为O(N)。

2、找出Top K

　　利用问题一中提到的最小堆排序可以实现。时间复杂度为O(N)+O(nlogK)，其中n为不重复的查询串。

三、海量数据处理---10亿数中找到最大的10000个数（文章地址YoferZhang）

　　1、使用最小堆排序，具体过程如问题一中算法3。时间复杂度为O(nlogn)+O(Nlogn)。其中N为1亿，n为10000。

　　2、优化

　　将10亿个数据分组存放，比如分成M组，然后每一组数据中找到Top K ，然后合并在一起，一块查找。查找过程使用最小堆排序。

 注：Top K的问题，通常比较好的方案是分治+Trie树/hash+小顶堆。

另外，LaoJiu_ 提到的BFPRT算法解决Top K的问题，最坏的时间复杂度为O(n)。

有用的链接：

教你如何迅速秒杀掉：99%的海量数据处理面试题

程序员编程艺术：第三章续、Top K算法问题的实现

hadoop mapreduce 解决 top K问题

海量数据处理算法（top K问题）

BFPRT 算法（TOP-K 问题）

Top k 问题