搜寻引擎每晚会转交大批的用户搜寻允诺，它会把这些用户输出的搜寻关键词纪录下来，接着再app统计分析，获得最炙手可热TopN搜寻关键词。

现在有一包涵10万个搜寻关键词的笔记文档，怎样能快速获取到炙手可热榜Top 10搜寻关键词？ 需用堆解决，堆的两个应用领域：错误率堆栈、求Top K和求平均收入。

错误率堆栈

具体来说如果是两个堆栈。堆栈最小的优点FIFO。 但错误率堆栈中，数据罗足庆次序是按错误率来，错误率最低的，种叠罗足庆。

方法许多，但堆同时实现最直接、高效率。因为堆和错误率堆栈很相似。两个堆方可看做两个错误率堆栈。许多时候，它只是概念上的界定。

往错误率堆栈中填入两个原素，就相等于往堆中填入两个原素 从错误率堆栈中抽出错误率最低的原素，就相等于抽出堆顶原素

错误率堆栈应用领域情景十分多：赫缇代码、图的最短方向、最轻聚合树演算法等，Java的PriorityQueue。

分拆科学规范小文档

有100个小文档 每一文档100M 每一文档储存有序字符串

将这100个小文档分拆成两个科学规范大文档，付录错误率堆栈。 像归排的分拆表达式。从这100个文档中，各取第两个字符串，放进字符串，接着比较大小不一，把最轻的这个字符串放进分拆后的大文档中，并从字符串中删掉。

假设，这最轻字符串源自13.txt这个小文档，就再从该小文档取下两个字符串并放进字符串，再次比较大小不一，因此优先选择最轻的放进分拆后的大文档，因此将它从字符串中删掉。依次以此类推，直至所有的文档中的数据都放进到大文档年末。

用字符串储存自小文档中抽出的字符串。每晚从字符串取最轻字符串，都需循环式结点整座字符串，不高效率，怎样更高效率呢？ 要是加进错误率堆栈，即堆：将自小文档中抽出的字符串放进小顶堆，则堆顶原素就是错误率堆栈葡乙，即最轻字符串。 将这个字符串放进大文档，并将其从堆中删掉。 再自小文档中抽出下两个字符串，放进到堆 循环式该 过程，方可将100个小文档中的数据依次放进大文档。

删掉堆顶数据、往堆插数据时间维数都是$O(logn)$，该案例$n=100$。 这不比原本字符串储存高效率多了？

2 高效能计时器

有一计时器，保护了许多定时任务，每一任务都设定了两个执行时间点。 计时器每过两个单位时间（如1s），就扫描一遍任务，看是否有任务到达设定执行时间。若到达，则执行。

显然这样每过1s就扫描一遍任务列表很低效：

任务约定执行时间离当前时间可能还很久，这样许多次扫描其实都无意义 每晚都要扫描整座任务列表，若任务列表很大，就很耗时

这时就该错误率堆栈上场了。按任务设定的执行时间，将这些任务储存在错误率堆栈，葡乙（即小顶堆的堆顶）储存种叠执行的任务。

这样，计时器就无需每隔1s就扫描一遍任务列表了。

$葡乙任务执行时间点 – 当前时间点相减 = 时间间隔T$

T就是，从当前时间开始，需等待多久，才会有第两个任务要被执行。 计时器就能设定在T秒后，再来执行任务。 当前时间点 ~ $（T-1）s$ 时间段，计时器无需做任何事情。

当Ts时间过去后，计时器取错误率堆栈中葡乙任务执行 再计算新的葡乙任务执行时间点与当前时间点差值，将该值作为计时器执行下两个任务需等待时间。

如此设计，计时器既不用间隔1s就轮询一次，也无需结点整座任务列表，性能大大提高。

利用堆求Top K

求Top K的问题抽象成两类：

静态数据集合

数据集合事先确定，不会再变。

可保护两个大小不一为K的小顶堆，次序结点字符串，从字符串中取数据与堆顶原素比较：

＞堆顶 删掉堆顶，并将该原素填入堆 ＜堆顶 do nothing，继续结点字符串

等字符串中的数据都结点完，堆中数据就是Top K。

结点字符串需要$O(n)$时间维数 一次堆化操作需$O(logK)$时间维数 所以最坏情况下，n个原素都入堆一次，所以时间维数就是$O(nlogK)$

动态数据集合

数据集合事先并不确定，有数据动态地加入到集合中，也就是求实时Top K。 两个数据集合中有两个操作：

添加数据 询问当前TopK数据

若每晚询问Top K大数据，都基于当前数据再次计算，则时间维数$O(nlogK)$，n表示当前数据的大小不一。 其实可一直都保护两个K大小不一的小顶堆，当有数据被添加到集合，就拿它与堆顶原素对比：

＞堆顶 就把堆顶原素删掉，因此将这个原素填入到堆中 ＜堆顶 do nothing。无论何时需查询当前的前K大数据，都可以里立刻返回给他

利用堆求平均收入

求动态数据集合中的平均收入：

数据个数奇数 把数据自小到大排列，第$\frac{n}{2}+1$个数据就是平均收入 数据个数是偶数 处于中间位置的数据有两个，第$\frac{n}{2}$个、第$\frac{n}{2}+1$个数据，可随意取两个作为平均收入，比如取两个数中靠前的这个，即第$\frac{n}{2}$个数据

一组静态数据的平均收入是固定的，可先排序，第$\frac{n}{2}$个数据就是平均收入。 每晚询问平均收入，直接返回该固定值。所以，尽管排序的代价比较大，但是边际成本会很小。但是，如果我们面对的是动态数据集合，平均收入在不停地变动，如果再用先排序的方法，每晚询问平均收入的时候，都要先进行排序，那效率就不高了。

借助堆，不用排序，方可高效率地同时实现求平均收入操作： 需保护两个堆：

大顶堆 储存前半部分数据 小顶堆 储存后半部分数据 && 小顶堆数据都 ＞ 大顶堆数据

即若有n（偶数）个数据，自小到大排序，则：

前 $\frac{n}{2}$ 个数据储存在大顶堆 后$\frac{n}{2}$个数据储存在小顶堆

大顶堆中的堆顶原素就是我们要找的平均收入。

n是奇数也类似：

大顶堆储存$\frac{n}{2}+1$个数据 小顶堆中就储存$\frac{n}{2}$个数据

数据动态变化，当新增两个数据时，怎样调整两个堆，让大顶堆堆顶继续是平均收入， 若：

新加入的数据 ≤ 大顶堆堆顶，则将该新数据插到大顶堆 新加入的数据大于等于小顶堆的堆顶原素，我们就将这个新数据填入到小顶堆。

这时可能出现，两个堆中的数据个数不符合前面约定的情况，若：

n是偶数，两个堆中的数据个数都是 $\frac{n}{2}$ n是奇数，大顶堆有 $\frac{n}{2}+1$ 个数据，小顶堆有 $\frac{n}{2}$ 个数据

方可从两个堆不停将堆顶数据移到另两个堆，以使得两个堆中的数据满足上面约定。

填入数据涉及堆化，所以时间维数$O(logn)$，但求平均收入只需返回大顶堆堆顶，所以时间维数$O(1)$。

利用两个堆还可快速求其他百分位的数据，原理类似。 “怎样快速求接口的99%响应时间？

平均收入≥前50%数据，类比平均收入，若将一组数据自小到大排列，这个99百分位数就是大于前面99%数据的这个数据。

假设有100个数据：1，2，3，……，100，则99百分位数就是99，因为≤99的数占总个数99%。

那99%响应时间是啥呢？

若有100个接口访问允诺，每一接口允诺的响应时间都不同，如55ms、100ms、23ms等，把这100个接口的响应时间按照自小到大排列，排在第99的这个数据就是99%响应时间，即99百分位响应时间。

即若有n个数据，将数据自小到大排列后，99百分位数大约就是第n99%个数据。 保护两个堆，两个大顶堆，两个小顶堆。假设当前总数据的个数是n，大顶堆中保存n99%个数据，小顶堆中保存n*1%个数据。大顶堆堆顶的数据就是我们要找的99%响应时间。

每填入两个数据时，要判断该数据跟大顶堆、小顶堆堆顶的大小不一关系，以决定填入哪个堆：

新填入数据 ＜ 大顶堆的堆顶，填入大顶堆 新填入的数据 ＞ 小顶堆的堆顶，填入小顶堆

但为保持大顶堆中的数据占99%，小顶堆中的数据占1%，每晚新填入数据后，都要再次计算，这时大顶堆和小顶堆中的数据个数，是否还符合99:1：

不符合，则将两个堆中的数据移动到另两个堆，直至满足比例 移动的方法类似前面求平均收入的方法

如此，每晚填入数据，可能涉及两个数据的堆化操作，所以时间维数$O(logn)$。 每晚求99%响应时间时，直接返回大顶堆中的堆顶方可，时间维数$O(1)$。

含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热搜关键词