Top K 问题

问题描述

有N(N>>10000)个整数,求出其中的前K个最大的数。

问题分析

需要前K个最大数，一定会有比较的过程。因此可以采用排序或者最小堆方式解决。

解决办法

1. 若数据量不太大，可以用常规的排序方式；
2. 若数据量太大，且中间数据无需保存，则可用最小堆解决；
3. 若数据量太大，且中间数据需要保存，则可用外部排序解决；

总结

Top K 问题常见于结果推荐。

参考文档

八大排序算法
Top K 小顶堆实现
Top K算法详细解析