搜索

什么是堆排序

gecimao 发表于 2019-08-05 19:17 | 查看: | 回复:

  可选中1个或多个下面的关键词,搜索相关资料。也可直接点“搜索资料”搜索整个问题。

  满足式(1)的称为极小化堆,或极小堆,或小堆,满足式(2)的称为极大化堆,或极大堆,或大堆。本节以极小化堆为例子进行讲解。

  堆与完全二叉树的关系:堆是n个元素(关键字)的序列,满足完全二叉树顺序存储中结点间的关系(双亲与子女序号间的关系)。

  既然堆顶元素(关键字)是最小元素,所以它是排序序列的最小元素,输出后,将其它元素再调整成堆,新的堆顶元素是排序序列的第二个元素。如此下去,通过堆,可将一个无序序列变为一个有序序列。因此,堆排序的基本问题是:

  将最后一个元素和堆顶元素交换(相当将堆顶元素输出)后,这时,从堆顶到倒数第二元素,除堆顶元素外,其余元素均符合堆的定义。下面采用筛选法,把包括堆顶元素在内的所有元素调成堆。大堆根

  { ‖假设R[i+1..m]中各元素满足堆的定义,本算法调整R[i]使序列

  具有n个结点的完全二叉树,其叶子结点被认为符合堆的定义,其最后一个非终端结点的编号是n/2,若从该结点开始,直到根结点,依次调用上面的筛选法,则可完成堆的建立。具体算法放在下面堆排序算法中。

  { ‖将堆顶记录和当前未经排序子序列R[1..i]中最后一个记录相互交换

本文链接:http://baumseelen.com/duipaixu/747.html
随机为您推荐歌词

联系我们 | 关于我们 | 网友投稿 | 版权声明 | 广告服务 | 站点统计 | 网站地图

版权声明:本站资源均来自互联网,如果侵犯了您的权益请与我们联系,我们将在24小时内删除。

Copyright @ 2012-2013 织梦猫 版权所有  Powered by Dedecms 5.7
渝ICP备10013703号  

回顶部