文章目錄

在搜索引擎中,要得到第一页的结果,可以使用堆这个数据结构来实现。在最小的K个数有这样的例子,这里需要将最小的K个数,改成最大的K个数实现。也就是说,建立一个大小为K的小顶堆,对于之后的元素,每个与堆顶比较,如果小于堆顶,则它不可能是最大的K个数之一,如果大于堆顶,则将堆顶替换,并重建小顶堆。之后剩下的K个元素就是最大的K个数,而堆顶是这K个元素中最小的。之后取出堆顶,得到这K个元素中最小的,然后重建小顶堆,再取出堆顶,得到这K个元素中第二小的,一直到堆中没有元素。

要得到第二页的结果,其实也是类似的。假设每页是K个元素,则先建立一个大小为2K的小顶堆。之后按照最大K个数的做法得到最大的2K个数。然后取出这2K个元素中的后面K个元素即是第二页的结果。

在Solr的QueryCompent.java中,mergeIds函数里就是这样做的。

文章目錄