堆式搜索引擎

罗伯特·弗洛伊德,1991年计算机先驱奖获得者,斯坦福大学计算机科学教授罗伯特弗洛伊德)1964年,他和J.Williams共同发明了著名的堆排序算法HEAPSORT[Williams 1964]。
首先给出了堆排序的定义,即下标为1、2、n的数组a称为“堆”,当且仅当该数组满足下列属性(称为“堆属性”);

如果把数组看作是完全二叉树的存储结构,则堆本质上是一个完全二叉树,它满足以下属性:树中任何非叶节点的关键字不大于(或小于)其左、右子节点的关键字(如果有)。例如,序列(10,15,56,25,30,70)和(70,56,30,25,15,10)分别满足堆属性(1)和(2),因此它们是堆。其中,根节点的关键字(又称“heap top”)是堆中所有节点中关键字最小的堆,称为“small root heap”(符合属性(1)),如图6-9所示;在堆中所有节点的关键字中,根节点的关键字(也称为“heap top”)是最大的,称为“大根堆”,符合堆属性(2),如图6-10所示。

接下来,我们以大根堆(可以理解为符合大根堆性质的数组)为例来研究堆排序的过程。
1。当当前堆中只剩下顶部(堆大小为1)时,堆排序结束,否则将(2)
2。顶部和尾部的更换
3。调整堆尾部以外的其余元素,使其符合大型根堆属性。转动(1)
我们可以研究大根堆的排序过程,如图6-10所示。顶部和尾部排列如图6-11所示。

继续用No改变当前堆的顶部,它一直持续到当前堆中只剩下堆的顶部,如图6-14所示。

堆排序除了具有内存副本较少的特点外,还具有“就地”排序的特点。换言之,排序过程只需要替换临时元素的存储成本,而不需要额外的存储成本。因此,堆排序的空间复杂度为0(1),可以概括为占用空间较少。
此外,堆排序对于top-N查询特别有用。也就是说,只需要对前n个元素进行排序,而不是所有元素都需要完全排序。例如,在图6-10所示的例子中,如果只需要对前两个元素进行排序,那么排序方法可以更改如下:
1。定义“已排序元素数”变量_2。当前堆中只剩下堆的顶部(当堆大小为1时),堆排序结束;否则,转到(2)
3_4。如果已排序,如果num==2,则堆排序结束;否则,转动(5)
5。调整堆末尾以外的其余元素,并调整当前堆以符合大型根堆的性质。排序完成后,数组的最后一位充实最大值,倒数第二位存储第二个大值,如图6-15所示。

因为其他位置不整齐,所以在最后两个位置排列好之后,排序可以停止。可以看出,堆排序只对前n个元素进行排序,计算量低,内存副本更少。
综上所述,堆排序具有内存拷贝少、占用社会空间少、适合top-N排序等特点,因此被用于查询词的计算和文档相关性排序。

搜索引擎的堆排序

版权声明:本文由守候(www.rc58.com.cn)发表于 2020年07月02日 ,本文共:1126字
转载请注明,本文转载自守候网络工作室:堆式搜索引擎

在线留言

说点什么吧
  • 全部评论(0
    还没有评论,快来抢沙发吧!