topk算法

寻找第k小元素 前k小元素 select_k

问题

对于海量数据到处理经常会涉及到 topK 问题。在设计数据结构和算法的时候，主要需要考虑的应该是当前算法（包括数据结构）跟给定情境（比如数据量级、数据类型）的适配程度，和当前问题最核心的瓶颈（如降低时间复杂度，还是降低空间复杂度）是什么。

首先，我们来举几个常见的 topK 问题的例子：

给定 100 个 int 数字，在其中找出最大的 10 个；
给定 10 亿个 int 数字，在其中找出最大的 10 个（这 10 个数字可以无序）；
给定 10 亿个 int 数字，在其中找出最大的 10 个（这 10 个数字依次排序）；
给定 10 亿个不重复的 int 数字，在其中找出最大的 10 个；
给定 10 个数组，每个数组中有 1 亿个 int 数字，在其中找出最大的 10 个；
给定 10 亿个 string 类型的数字，在其中找出最大的 10 个（仅需要查 1 次）；
给定 10 亿个 string 类型的数字，在其中找出最大的 k 个（需要反复多次查询，其中 k 是一个随机数字）。
1
2
3
4
5
6
7

上面这些问题看起来很相似，但是解决的方式却千差万别。稍有不慎，就可能使得 topK 问题成为系统的瓶颈。不过也不用太担心，接下来我会总结几种常见的解决思路，遇到问题的时候，大家把这些基础思路融会贯通并且杂糅组合，即可做到见招拆招。

最基本思路

将N个数进行完全排序，从中选出排在前K的元素即为所求。有了这个思路，我们可以选择相应的排序算法进行处理，目前来看快速排序，堆排序和归并排序都能达到O(NlogN)的时间复杂度。

优先队列

选择其中前K个数作为数据池，后面的N-K个数与这K个数进行比较，若小于/大于其中的任何一个数，则进行替换。这种思路的算法复杂度是O(N*K).
剩余的N-K个数与前面K个数比较的时候，是顺序比较的，算法复杂度是O(N*K)。

“冒泡排序”获取TopK

可以避免对所有数据进行排序，只排序部分；
冒泡排序是每一轮排序都会获得一个最大值，则K轮排序即可获得TopK。
时间复杂度O(N*K)

小根堆

堆排序是通过维护大顶堆或者小顶堆来实现的。堆排序法来解决N个数中的TopK的思路是：

1. 先随机取出N个数中的K个数，将这K个数构造为小顶堆，那么堆顶的数肯定就是这K个数中最小的数了
2. 然后再将剩下的N-K个数与堆顶进行比较，如果大于堆顶，那么说明该数有机会成为TopK，就更新堆顶为该数，此时由于小顶堆的性质可能被破坏，就还需要调整堆；

//添加每个数到小根堆，小根堆堆化
//如果 num < 堆顶(最小元素)，会堆化到堆顶，如果 num > 堆顶，会堆化到堆顶之下
queue.add(num);		
if(queue.size()>k) queue.poll();    //把 堆中最小的 poll 了
1
2
3
4

4. 否则说明这个数最多只能成为Top K+1，因此就不用管它 。
5. 然后就将下一个数与当前堆顶的数作比较，根据大小关系如上面所述方法进行操作，直到N-K个数都遍历完，此时还在堆中的K个数就是TopK了。

对K个元素进行建堆，时间复杂度为O(K)；
然后对剩下的N-K个数对堆顶进行比较及更新，最好情况下当然是都不需要调整了，那么时间复杂度就只是遍历这N-K个数的O(N-K)，这样总体的时间复杂度就是O(N)
而在最坏情况下，N-K个数都需要更新堆顶，每次调整堆的时间复杂度为logK，因此此时时间复杂度就是NlogK了，总的时间复杂度就是O(K)+O(NlogK)≈O(NlogK)

一般来说企业中都采用该策略处理topK问题，因为该算法不需要一次将原数组中的内容全部加载到内存中，而这正是海量数据处理必然会面临的一个关卡。

快速选择算法

快速选择算法 - Quick select

利用快速排序的partition分划函数找到分划位置K，则其前面的内容即为所求。该算法是一种非常有效的处理方式，时间复杂度是O(N)（证明可以参考算法导论书籍）。对于能一次加载到内存中的数组，该策略非常优秀。

分治法 + 快速选择算法

1. 比如有10亿的数据，找处Top1000，我们先将10亿的数据分成1000份，每份100万条数据。
2. 在每一份中找出对应的Top 1000，整合到一个数组中，得到100万条数据，这样过滤掉了99%的数据。
3. 使用快速排序对这100万条数据进行”一轮“排序，一轮排序之后指针的位置指向的数字假设为S，会将数组分为两部分，一部分大于S记作Si，一部分小于S记作Sj。
4. 如果Si元素个数大于1000，我们对Si数组再进行一轮排序，再次将Si分成了Sii和Sjj。如果Si的元素小于1000，则我们需要在Sj中获取1000-count(Si)个元素的，也就是对Sj进行排序
5. 如此递归下去即可获得Top-K。

总结

优先队列。前K个数作为数据池，后面的N-K个数与这K个数进行比较，若小于/大于其中的任何一个数，则进行替换			O(N*K)

冒泡排序，O(N*K)

使用最大最小堆。求最大的数用最小堆，求最小的数用最大堆。     O(K)+O(NlogK)≈O(NlogK)
		一次堆化的时间复杂度为 O(logK)

Quick Select算法。使用类似快排的思路，根据pivot划分数组。  O(N)	


使用排序方法，排序后再寻找top K元素。  				     O(NlogN)
使用选择排序的思想，对前K个元素部分排序。
将1000.....个数分成m组，每组寻找top K个数，得到m×K个数，在这m×k个数分治。
1
2
3
4
5
6
7
8
9
10
11
12
13