编程之美2.5节后面的两个扩展问题
1
在搜索引擎中，网络上的每个网页都有“权威性”权重，如page rank。如果
我们需要寻找权重最大的K个网页，而网页的权重会不断地更新，那么算
法要如何变动以达到快速更新（incremental update）并及时返回权重最大
的K个网页？
提示：堆排序？当每一个网页权重更新的时候，更新堆。还有更好的方法
吗？


2
在实际应用中，还有一个“精确度”的问题。我们可能并不需要返回严格意义
上的最大的K个元素，在边界位置允许出现一些误差。当用户输入一个query
的时候，对于每一个文档d 来说，它跟这个query之间都有一个相关性衡量权
重f （query, d）。搜索引擎需要返回给用户的就是相关性权重最大的K个
网页。如果每页10个网页，用户不会关心第1000页开外搜索结果的“精确
度”，稍有误差是可以接受的。比如我们可以返回相关性第10 001大的网页，
而不是第9999大的。在这种情况下，算法该如何改进才能更快更有效率
呢？网页的数目可能大到一台机器无法容纳得下，这时怎么办呢？
提示：归并排序？如果每台机器都返回最相关的K 个文档，那么所有机器
上最相关K 个文档的并集肯定包含全集中最相关的K 个文档。由于边界
情况并不需要非常精确，如果每台机器返回最好的K’个文档，那么K’应
该如何取值，以达到我们返回最相关的90%*K 个文档是完全精确的，或
者最终返回的最相关的K 个文档精确度超过90%（最相关的K 个文档中
写书评，赢取《编程之美--微软技术面试心得》www.ieee.org.cn/BCZM.asp
90%以上在全集中相关性的确排在前K），或者最终返回的最相关的K 个
文档最差的相关性排序没有超出110%*K。


没什么思路特来请教~~~~~~~~~~

[解决办法]
http://www.cnblogs.com/zhjp11/archive/2010/02/26/1674227.html
仅供参考