利用堆求 TopK 问题及其应用案例解决思路

利用堆求 TopK

堆的一个非常重要和经典的应用场景，那就是“求 Top K 问题”。

我把这种求 Top K 的问题抽象成两类。一类是针对静态数据集合，也就是说数据集合事先确定，不会再变。另一类是针对动态数据集合，也就是说数据集合事先并不确定，有数据动态地加入到集合中。

针对静态数据，如何在一个包含 n 个数据的数组中，查找前 K 大数据呢？

我们可以维护一个大小为 K 的小顶堆，顺序遍历数组，从数组中取出取数据与堆顶元素比较。如果比堆顶元素大，我们就把堆顶元素删除，并且将这个元素插入到堆中；如果比堆顶元素小，则不做处理，继续遍历数组。这样等数组中的数据都遍历完之后，堆中的数据就是前 K 大数据了。
遍历数组需要 O(n) 的时间复杂度，一次堆化操作需要 O(logK) 的时间复杂度，所以最坏情况下，n 个元素都入堆一次，所以时间复杂度就是 O(nlogK)。

针对动态数据求得 Top K 就是实时 Top K，怎么理解呢？

举一个例子：一个数据集合中有两个操作，一个是添加数据，另一个询问当前的前 K 大数据。
如果每次询问前 K 大数据，都是基于当前的数据重新计算的话，那时间复杂度就是 O(nlogK)，n 表示当前的数据的大小。

实际上，我们可以一直都维护一个 K 大小的小顶堆，当有数据被添加到集合中时，我们就拿它与堆顶的元素对比。如果比堆顶元素大，我们就把堆顶元素删除，并且将这个元素插入到堆中；如果比堆顶
元素小，则不做处理。这样，无论任何时候需要查询当前的前 K 大数据，我们都可以实时返回。

TopK 应用案例

案例说明

了解了上面堆的一些应用场景的处理思路之后，再来看下这个问题：假设现在有一个包含 10 亿个搜索关键词的日志文件，如何快速获取到 Top10 最热门的搜索关键词呢？

解决此问题，可以有很多相对比较高级的解决方法，比如使用 MapReduce 等。现在要求将处理的场景限定为单个机器，可使用的内存限定为 1GB，则此问题该如何解决呢？

首先因为用户搜索的是关键词，应该有很多可能都是重复的，所以首先想到的是要统计每个搜索关键词出现的频率，然后可以通过散列表、平衡二叉查找树或者其他一些支持快速查找、插入的数据结构，来记录关键词及其出现的次数。

选用散列表，解决思路及不足之处

假定选用散列表，解决思路如下：

1. 就顺序扫描这 10 亿个搜索关键词，每扫描到某个关键词时，就去散列表中查询；
2. 如果存在，则将对应的关键词的次数加一；如果不存在，就将它插入到散列表，并记录次数为 1；
3. 以此类推，等遍历完这 10 亿个搜索关键词之后，散列表中就存储了不重复的搜索关键词以及出现的次数。
4. 然后，再根据前面讲的用堆求 Top K 的方法，建立一个大小为 10 的小顶堆，遍历散列表，依次取出每个搜索关键词及对应出现的次数；
5. 然后与堆顶的搜索关键词对比，如果出现次数比堆顶搜索关键词的次数多，那就删除堆顶的关键词，将这个出现次数更多的关键词加入到堆中；
6. 以此类推，当遍历完整个散列表中的搜索关键词之后，堆中的搜索关键词就是出现次数最多的 Top 10 搜索关键词了。

回过头分析下，上面的解决思路其实是不严谨的，或者说是存在漏洞的。怎么说呢，10 亿的关键词还是很多的，假设 10 亿条搜索关键词中不重复的有 1 亿条，如果每个搜索关键词的平均长度是 50 个字节，那存储 1 亿个关键词大概需要 5GB 的内存空间，而散列表由于需要避免频繁冲突，不会选择太大的装载因子，所以消耗的内存空间可能就更多了。而机器的可用内存空间只有 1GB，所以是无法一次性将所有的搜索关键词加入到内存中的。这个时候该做怎样的优化呢？

哈希算法 + 散列表 + 堆 实现获取 Top10 最热门搜索关键词的思路

哈希算法就派上用场了，相同数据经过哈希算法得到的哈希值是一样的。根据哈希算法的这一特点，可以先将 10 亿条搜索关键词通过哈希算法分片到 10 个文
件中。具体实现流程如下：

1. 创建 10 个空文件 00，01，02，……，09；
2. 遍历这 10 亿个关键词，并且通过某个哈希算法对其求哈希值；
3. 然后哈希值跟 10 取模，得到的结果就是这个搜索关键词应该被分到的文件编号。
4. 对这 10 亿个关键词分片之后，每个文件大概有 1 亿的关键词，去除掉重复的，可能也就只有 1000 万个左右，每个关键词平均 50 个字节，所以总的大小就是 500MB，所以 1GB 的内存完全可以放得下；
5. 针对每个包含 1 亿条搜索关键词的文件，利用散列表和堆，分别求出 Top 10；
6. 最后把这个 10 个 Top 10 放在一块，取这 100 个关键词中出现次数最多的 10 个即可。