最大堆---实现一个简化的搜索提示系统。给定一个包含了用户query的日志文件，对于输入的任意一个字符串s，输出以s为前缀的在日志中出现频率最高的前10条query。
本文共 1252 字，大约阅读时间需要 4 分钟。
实现一个简化的搜索提示系统。给定一个包含了用户query的日志文件，对于输入的任意一个字符串s，输出以s为前缀的在日志中出现频率最高的前10条query。
由于是分布式系统，假设至少有26台机器，每个机器存储以26个字母开头的query日志文件（如机器1存的是a字母开头的，机器2存的是以b字母开头的……）
每个机器上维护着一张哈希表，对于每条query, 在哈希表表中存放其地址（哈希地址为链式的），并对其进行排序，按频率由高到低进行排序。
当用户进行搜索时，可以很快定位到某台机器，并根据哈希表，返回出现频率最高的前10条query。
提示：
1、可以预处理日志
2、假设query不超过10亿条，每个query不超过50字节。
3、考虑在大查询量的情况下如何实现分布式服务
用JS监控input输入框的内容变化，用户输入或者删除字符（输入串的发生变化）就触发异步Javascript提交输入内容到后台，引发后台查询。然后再讲查询结果出现频率最高的前10条query展现给用户提示。 首先有26台服务器分别存储26个字母开头的query。所以首先要设计一个接收用户请求的服务器，这台服务器可以根据用户请求的首字母将查询请求分发给对应26台服务器中的一个（相当于查询请求的路由功能）。 假设query不超过10亿条，每个query不超过50字节。也就是query文件不超过50G，分在26台机器上也就是每台机器上的query文件不超过2G。 每个机器上维护着一张哈希表，对于每条query, 在哈希表表中存放其地址。收到每个query做hash运算可以找到query对应的地址。对应每个query存储两项信息，即query本身和被查询次数，也就是类似query:times这样的存储格式。 下面做预处理：26台机器都对自身存储的query进行遍历，分别找出a到z开头query出现频率最高的top10，这样的查询一次遍历就能找到，时间复杂度为O（N）。然后对找到的top10在内存中构建一个最小堆。其他非top10的query无需做排序处理。到这里预处理完成。 1，以给出搜索提示的异步Javascript提交的查询，这种查询直接返回最小堆中的10个query词条即可。 2，用户最终提交的查询（即用户输入完毕点击搜索按钮提交的查询），这种查询的query是用户最终查询的词条，这样的查询应该引起后台存储的对应query频率的变化。当一个query到达的时候，先用hash运算找到他的位置和对应的频率，hash操作时间复杂度是O(1),然后对应的次数+1，然后用这个+1的次数与最小堆中首个元素比较，如果大于最小堆首个元素，与最小堆中首个元素交换，然后最小堆做更新操作，保证最小堆的特性。否则不操作。这样最小堆中维护的10个query始终是这台机器上频率最高的，查询时返回这10个query词条即可。 转载地址：http://kziab.baihongyu.com/