TopK问题是一个经典的海量数据处理问题，比如微博热搜每隔10分钟都会更新出排行前10的热门搜索信息，再或者通过大数据找出一个地区最爱吃的水果等，都可以使用TopK问题来解决，其核心思想就是最小堆的引入。

在海量数据中找出出现频率最高的前K个数，或者从海量数据中找出最大的前K个数，这类问题通常被称为TopK问题。

下面我们通过一个简单的例子来说明：假如面试官给你100W个数据，请找出其最大的前K个数，而且现在只有1M的空间？

在32位操作系统中，默认一个字节为4个字节，则有下列运算：

NeedSize = 100W * 4 / 1024 /1024 = 4M

计算结果大约等于4M，很显然1M的空间根本不够。也就是说，即使用最复杂的方法你也无法找到一个合适的空间来存储，因此引入了最小堆数据结构。

下面我只说实现的核心思路，对此有不理解的请查看最大堆和最小堆的相关性质。思路如下：

（1）定义两个数组，arr用于存储海量数据，top用于存储最小堆（底层可以借助vector）

（2）将海量数据的前K个元素先填满top堆

（3）调整top堆为最小堆结构

（4）通过遍历将新数据与堆顶元素（此时堆顶元素是堆里最小的数据）进行比较，大于堆顶就入堆，并向下调整堆结构

（5）遍历结束，则堆中的元素即n个数中最大的前K个

问题描述：本公司现在要给公司员工发福利，在员工工作时间会提供大量的水果供员工补充营养。由于水果种类比较多，但是又不知道哪种水果比较受欢迎，然后公司就让每个员工报告了自己最爱吃的K种水果，并且告知已经将所有员工喜欢的水果存储于一个数组中，然后让我们统计出所有水果出现的次数，并且求出大家最喜欢吃的前K种水果。

算法分析：往往笔试过程中，要求在很短的时间内写出一个算法，直接调用标准库里的函数是比较方便的，比如这道题就是对STL中三种容器的考察，具体步骤如下：

（1）首先，使用vector来存储所有的水果。

（2）其次，采用map将vector中存在的水果的数量统计出来，map支持下标访问。

（3）最后，通过优先级队列来建立小堆，然后就是TopK问题。

代码实现：