Topk

TopK： 从一堆数里面找到前k个最大的数

小数据集

可以用快排的partition实现，也可以用堆排。如果语言支持优先队列，直接用优先队列更加方便

大数据集

数据量大的时候用快排就不合适了，因为数据的大小可能超出了内存的限制。 可以利用堆排或者优先队列解决。优先队列，如C++ STL的，内部实现其实也是heap. 假设现在有1G的数据量存储在大文件内，要取top 10. 先看在单机上用goroutine如何处理

1. 大文件切割成10个100M的小文件

2. 启动10个goroutine, 分别处理10个小文件，得到各自的top10。 对每个goroutine:

2.1 维护一个大小为10的大顶堆，读取小文件的每一行

2.2 如果堆大小不足10个，

直接堆排序

2.3 如果堆大小等于10个，

如果堆顶元素小于待处理的数字，移除堆顶元素，将待处理的数字放入堆，进行堆排序。 如果堆顶元素大于等于待处理的数字，不作处理。

2.4 将堆元素写入新文件，即为堆数据文件

3. 对10个堆数据文件两两归并排序，一直到合并为一个文件, 该文件包含10个数字，即为最终的top 10。