给定一个file， 查找出里面出现频率最高的10个单词_计算出现频率最高的10个单词

之前已经总结了给定一组数字， 如何在线性时间内找到第k小的数字。

这两个问题看似有十分subtle的关系。 很显然这里是找最大的前K个单词。 单词相当于卫星数据， 直接对单词的键值， 即频率排序啦。 

现在我们对这个求top K frequent words做一个小小的总结。

方法一： minheap + external sort(即小顶堆 + 外部排序）

之所以使用外部排序， 是因为考虑到文件很大， 无法一次装入内存中。

首先第一步就是统计单词的频率。 例如 “the”, "word"等等单词。 例如 [1233, "the"]， 表示单词“the”出现了1233次。统计完成之后， 我们开始对单词的频率进行排序。 可以使用一个大小为K的minHeap。 一旦有一个单词的频率大于minHeap的root(对应着小顶堆中， 关键字（即频率最小（的单词））), 我们就用这个新加进来的单词替换掉root， 然后再调整heap以得到满足heap性质的新的heap。 

方法二： min heap + hashmap（C++11中， 对应着unordered_map）

使用哈希。 首先把所有的单词一个一个的映射到一个hash table(哈希表)中。 如果一个单词已经出现在表中， 就对count加1操作。 最终， 映射完成之后， 我们得到一个具有文件中所有的单词的个数的统计信息。 我们只需要遍历哈希表， 返回具有最大的Count的k个单词即可。

方法三： Trie+ MinHeap(字典树 + 最小堆）

我还不知道Trie是干嘛的。 先恶补一下, 其实很简单。

Trie又被称为字典树， 或者称为前缀树。

为了理解Trie, 首先看看我们可以用Trie干嘛的呀。 

（1）Tr