搜索引擎每天接收大量用户搜索请求，把这些用户输入的搜索关键词记录，再离线统计分析，得到热门TopN搜索关键词。
现有一包含10亿个搜索关键词的日志文件，如何快速获取热门榜Top 10搜索关键词？ 可用堆解决，堆的几个应用：优先级队列、求Top K和求中位数。
1 优先级队列
优先级队数据出队顺序按优先级，优先级高的先出队。
堆实现最为直接、高效。堆和优先级队列相似。一个堆即可看作一个优先级队列。很多时候，它们只是概念上的区分：
- 往优先级队列中插入一个元素，相当于往堆中插入一个元素
- 从优先级队列中取出优先级最高元素，相当于取出堆顶
优先级队列应用场景：赫夫曼编码、图最短路径、最小生成树算法等，Java PriorityQueue。
2 合并有序小文件
- 100个小文件
- 每个文件100M
- 每个文件存储有序字符串
将这100个小文件合并成一个有序大文件，就用到优先级队列。像归排的合并函数。从这100个文件中，各取第一个字符串，放入数组，然后比较大小，把最小的那个字符串放入合并后的大文件，并从数组中删除。
假设，这最小字符串来自13.txt这个小文件，就再从该小文件取下一个字符串并放入数组，重新比较大小，并且选择最小的放入合并后的大文件，并且将它从数组中删除。依次类推，直到所有的文件中的数据都放入到大文件。
用数组存储从小文件中取出的字符串。每次从数组取最小字符串，都需循环遍历整个数组，能更高效吗？ 优先级队列，即堆：
- 将从小文件中取出的字符串放入小顶堆，则堆顶元素就是优先级队列的队首，即最小字符串
- 将这个字符串放入大文件，并将其从堆中删除
- 再从小文件中取出下一个字符串，放入到堆
- 循环该过程，即可将100个小文件中的数据依次放入大文件
删除堆顶数据、往堆插数据时间复杂度都是
，该案例
。
3 高性能定时器
维护很多定时任务，每个任务都设定了一个执行时间点。 定时器每过一个单位时间（如1s），就扫描一遍任务，看是否有任务到达设定执行时间。若到达，则执行：
显然这样每1s就扫描一遍任务列表很低效：
- 任务约定执行时间离当前时间可能还很久，很多次扫描无意义
- 每次都扫描整个任务列表，若任务列表很大，耗时多
这时就该优先级队列。按任务设定的执行时间，将这些任务存储在优先级队列，队首（即小顶堆的堆顶）存储最先执行的任务。定时器就无需每隔1s就扫描一遍任务列表。
T就是，从当前时间开始，需等待多久，才会有第一个任务要被执行。 定时器就能设定在T秒后，再来执行任务。 当前时间点 ~
时间段，定时器无需做任何事情。
当Ts时间过去后，定时器取优先级队列中队首任务执行，再计算新的队首任务执行时间点与当前时间点差值，将该值作为定时器执行下一个任务需等待时间。
定时器：
- 既不用间隔1s就轮询一次
- 也无需遍历整个任务列表
4 利用堆求Top K
Top K问题抽象成两类：
4.1 静态数据集合
数据集合事先确定，不会再变。
可维护一个大小为K的小顶堆，顺序遍历数组，从数组中取数据与堆顶元素比较：
- ＞堆顶 删除堆顶，并将该元素插入堆
- ＜堆顶 do nothing，继续遍历数组
等数组中的数据都遍历完，堆中数据就是Top K。
遍历数组需
，一次堆化操作需
，最坏情况：n个元素都入堆一次，即
。
4.2 动态数据集合
数据集合事先并不确定，有数据动态地加入到集合中，也就是求实时Top K。 一个数据集合中有两个操作：
- 添加数据
- 询问当前TopK数据
若每次询问Top K大数据，都基于当前数据重新计算，则时间复杂度
，n表示当前数据的大小。 可一直都维护一个K大小的小顶堆，当有数据被添加到集合，就拿它与堆顶元素对比：
- ＞堆顶 就把堆顶元素删除，并且将这个元素插入到堆中
- ＜堆顶 do nothing。无论何时需查询当前的前K大数据，都可以里立刻返回给他
5 利用堆求中位数
求动态数据集合中的中位数：
- 数据个数奇数 把数据从小到大排列，第
个数据就是中位数
- 数据个数是偶数 处于中间位置的数据有两个，第
个、第
个数据，可随意取一个作为中位数，比如取两个数中靠前的那个，即第
个数据
一组静态数据的中位数是固定的，可先排序，第
个数据就是中位数。 每次询问中位数，直接返回该固定值。所以，尽管排序代价大，但边际成本小。但若动态数据集合，中位数在不停变动，如再用先排序的方法，每次询问中位数都要先排序，效率就不高。
利用堆，不用排序，即可高效实现求中位数操作，需维护两个堆：
- 大顶堆 存储前半部分数据
- 小顶堆 存储后半部分数据 && 小顶堆数据都 ＞ 大顶堆数据
即若有n（偶数）个数据，从小到大排序，则：
- 前
个数据存储在大顶堆
- 后
个数据存储在小顶堆
大顶堆中的堆顶元素就是我们要找的中位数。
n是奇数也类似：
- 大顶堆存储
个数据
- 小顶堆中就存储
个数据
数据动态变化，当新增一个数据时，如何调整两个堆，让大顶堆堆顶继续是中位数， 若：
- 新加入的数据 ≤ 大顶堆堆顶，则将该新数据插到大顶堆
- 新加入的数据大于等于小顶堆的堆顶元素，我们就将这个新数据插入到小顶堆。
这时可能出现，两个堆中的数据个数不符合前面约定的情况，若：
- n是偶数，两个堆中的数据个数都是
- n是奇数，大顶堆有
个数据，小顶堆有
个数据
即可从一个堆不停将堆顶数据移到另一个堆，以使得两个堆中的数据满足上面约定。
插入数据涉及堆化，所以时间复杂度
，但求中位数只需返回大顶堆堆顶，所以时间复杂度
。
利用两个堆还可快速求其他百分位的数据，原理类似。
“如何快速求接口的99%响应时间？
中位数≥前50%数据，类比中位数，若将一组数据从小到大排列，这个99百分位数就是大于前面99%数据的那个数据。
假设有100个数据：1，2，3，……，100，则99百分位数就是99，因为≤99的数占总个数99%。
维护两个堆：
- 一个大顶堆
- 一个小顶堆
假设当前总数据的个数是n，大顶堆中保存n99%个数据，小顶堆中保存n1%个数据。大顶堆堆顶的数据就是我们要找的99%响应时间。
每插入一个数据时，要判断该数据跟大顶堆、小顶堆堆顶的大小关系，以决定插入哪个堆：
- 新插入数据 ＜ 大顶堆的堆顶，插入大顶堆
- 新插入的数据 ＞ 小顶堆的堆顶，插入小顶堆
但为保持大顶堆中的数据占99%，小顶堆中的数据占1%，每次新插入数据后，都要重新计算，这时大顶堆和小顶堆中的数据个数，是否还符合99:1：
- 不符合，则将一个堆中的数据移动到另一个堆，直到满足比例 移动的方法类似前面求中位数的方法
如此，每次插入数据，可能涉及几个数据的堆化操作，所以时间复杂度
。 每次求99%响应时间时，直接返回大顶堆中的堆顶即可，时间复杂度
。
6 10亿个搜索关键词日志文件，获取Top 10
很多人说MapReduce，但若将场景限定为单机，可使用内存为1GB，咋办？
用户搜索的关键词很多是重复的，所以先统计每个搜索关键词出现频率。 可通过散列表、平衡二叉查找树或其他一些支持快速查找、插入的数据结构，记录关键词及其出现次数。
假设散列表。 顺序扫描这10亿个搜索关键词。当扫描到某关键词，去散列表中查询：
- 存在，对应次数加一
- 不存在，插入散列表，并记录次数1
等遍历完这10亿个搜索关键词后，散列表就存储了不重复的搜索关键词及出现次数。
再根据堆求Top K方案，建立一个大小为10小顶堆，遍历散列表，依次取出每个搜索关键词及对应出现次数，然后与堆顶搜索关键词对比：
- 出现次数 ＞ 堆顶搜索关键词的次数 删除堆顶关键词，将该出现次数更多的关键词入堆。
以此类推，当遍历完整个散列表中的搜索关键词之后，堆中的搜索关键词就是出现次数最多的Top 10搜索关键词了。
但其实有问题。10亿的关键词还是很多的。 假设10亿条搜索关键词中不重复的有1亿条，如果每个搜索关键词的平均长度是50个字节，那存储1亿个关键词起码需要5G内存，而散列表因为要避免频繁冲突，不会选择太大的装载因子，所以消耗的内存空间就更多了。 而机器只有1G可用内存，无法一次性将所有的搜索关键词加入内存。
何解？
因为相同数据经哈希算法后的哈希值相同，可将10亿条搜索关键词先通过哈希算法分片到10个文件：
- 创建10个空文件：00~09
- 遍历这10亿个关键词，并通过某哈希算法求哈希值
- 哈希值同10取模，结果就是该搜索关键词应被分到的文件编号
10亿关键词分片后，每个文件都只有1亿关键词，去掉重复的，可能就剩1000万，每个关键词平均50个字节，总大小500M，1G内存够。
针对每个包含1亿条搜索关键词的文件：
- 利用散列表和堆，分别求Top 10
- 10个Top 10放一起，取这100个关键词中，出现次数Top 10关键词，即得10亿数据的Top 10热搜关键词
