深圳SEO
欢迎您光临!

搜索引擎的堆排序

1991年计算机先驱奖获得者、斯坦福大学计算机科学系教授罗伯特弗洛伊德(robert w.floyd)和威廉姆斯(j.willianms)在1964年共同发明了著名的堆排序算法heapsort[willioms 1964]。
首先给出堆排序定义,即大小为n的数组a,下标依次为1,2,…..,n,称为“堆”,当且仅当数组满足如下性质(简称为“堆性质”);

堆性质

若将此数组看做是一棵完全二叉树的存储结构,则堆实质上是满足如下性质的完全二叉树,即树中任意一个非叶结点的关键字均不大于(或小于)其左右孩子(若存在)结点的关键字。例如序列(10,15,56,25,30,70)和(70,56,30,25,15,10)分别满足堆性质(1)和(2),故它们均是堆。其中根结点(也称为“堆顶”)的关键字是堆中所有结点关键字中最小者的堆,称为“小根堆”(符合性质(1)),如图6-9所示;根结点(也称为“堆顶”)的关键字是堆中所有结点关键字中最大者,称为“大根堆”,它符合堆性质(2),如图6-10所示。

小根堆

接下来以大根堆(可以理解为符合大根堆性质的数组)为例,考察堆排序的过程。
1.当前堆仅剩下堆顶(堆大小为1)时堆排序结束,否则转(2)
2.堆顶和堆尾置换
3.将除堆尾以外的余下元素调整,并符合大根堆性质,转(1)
不妨考察图6-10所示的大根堆的排序过程,堆顶和堆尾置换如图6-11所示。

大根堆

深圳SEO

深圳SEO

继续将当前堆的堆顶和当前堆的堆尾5号位置换(原堆尾为6号位,注意每次执行一个操作,当前堆尾位置减1),调整成大根堆。周而复始,直到当前堆中只剩下堆顶时排序结束,如图6-14所示。

当前堆的堆顶和当前堆的堆尾

除了具有内存拷贝少的特点,堆排序还具有“就地”排序(in-place)的特点。即排序过程只需要一个置换的临时元素的存储开销,不需要额外的存储开销。因此堆排序的空间复杂度是0(1),这个特点可以归纳为空间占用少。
此外,堆排序特别有利于进行top-n的查询。即仅需要排序前n个元素,而不需要完全排序所有的元素。例如在如图6-10所示的例子中,如果只需要排序前两个元素,那么排序的方法可以改为:
1.定义“已经排序的元素个数”变量sorted_num++,并初始化为0
2.当前堆仅剩下堆顶(堆大小为1时),堆排序结束;否则转(2)
3.堆顶和堆尾置换,sorted_num++
4.若sorted_num==2,堆排序结束;否则转(5)
5.将除堆尾以外的余下的元素调整,并调整当前堆使之符合大根堆性质,转(1)
排序结束后,数组末位丰放最大值,倒数第2位存放次大值(second-large),如图6-15所示。

深圳SEO:second-large

由于其他位置是否有序并不关心,所以排序可以在排好倒数第2位后停止。可见堆排序在仅排序前n个元素具有计算量低,内存拷贝少的性质。
综上所述,堆排序具有内存拷贝少,社额外空间占用少并适合top-n的排序的特点,因此被用于查询词和文档相关度排序的计算中。

本文出自深圳SEO公司,未经允许不得转载:深圳SEO公司-深圳SEO服务公司 » 搜索引擎的堆排序
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址