




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、堆和堆排序主讲人:林秋照堆的定义堆可以定义为一颗二叉树,树的节点中包含键(每个节点一个键),并且满足两个条件:1、树的形状要求这棵二叉树是基本完备的(或者简称为完全二叉树),这意味着,树的每一层都是满的,除了最后一层最右边的元素有可能缺位。2、父母优势要求每一个节点的键都要大于或等于它的子女的键(对于任何叶子我们认为这个条件都是自动满足的)。3rir2i r2i+1 1236276549817355403498例如:是堆14不4例 (96,83,27,38,11,9)例 (13,38,27,50,76,65,49,97)堆序列是完全二叉树,则堆序列是完全二叉树,则堆顶元素(完全二叉堆顶元素(完
2、全二叉树的根)必为序列中树的根)必为序列中n个元素的最小值或最大个元素的最小值或最大值值如下图,是一个堆和数组的相互关系:二叉堆一般分为两种:最大堆和最小堆。两种堆内部的数据都要满足自己的特点。比如最大堆的特点是,每个父节点的元素值都不小于其孩子结点(如果存在)的元素值,因此,最大堆的最大元素值出现在根结点(堆顶)最小堆的性质与最大堆恰好相反。堆的重要特性1、只存在一棵N个节点的完全二叉树。它的高度等于堆的根总是包含了堆得最大元素。3、堆的一个节点以及该节点的子孙也是一个堆。4、可以用数组来实现堆,方法是用从上向下、从左向右的方式来记录堆的元素。可以在这种数组从1到N的位置上存放堆元素,留下H
3、0,要么让它空着,要么在其中放一个限位器,它的值大于堆中的任何一个元素。堆的构造堆的构造主要有两种方法。第一种是自底向上堆构造。在初始化一棵包含N个节点的完全二叉树时,我们就按照给定的顺序来放置键;然后按照下面的方法对树进行“堆化”。从最后的父母节点开始到根为止,该算法检查这些节点的键是否满足父母优势要求。如果该节点不满足,该算法把节点的键K和它子女的最大键进行交换,然后再检查在新位置上,K是不是满足父母优势要求。这个过程一直持续到,对K的父母优势要求满足为止(最终它必须满足,因为对于每个叶子中的键来说,这个条件是自动满足的)。对于以当前父母节点为根的子树,在完成它的“堆化”以后,该算法对于该
4、节点的直接前趋进行同样的操作。在对树的根完成了这种操作以后,该算法就停止了。8建堆是一个从下往上进行“筛选”的过程。40554973816436122798例如: 原始序列为(40,55,49,73,12,27,78,81,64,36)123681734998817355l左/右子树都已经调整为堆l最后只要调整根结点,使整个二叉树是个“堆”即可。9849406436122799881497355641236274012输出98( 98 和 12 进行互换)之后,它就不是堆了需要对它进行“筛选”98128173641298比较比较大顶堆大顶堆调节过程:调节过程:大顶堆的排序结果是升序排序大顶堆的
5、排序结果是升序排序另一种算法(效率较低)通过把新的键连续插入预先构造好的堆,来构造一个新堆。首先,把一个包含键K的新节点附加在当前堆得最后一个叶子后面。然后按照下面的方法把K筛选到他的适当位置。拿K和它父母的键做比较:如果后者大于等于K,算法停止(该机=结构已经是一个堆了);否则,交换这两个键并把K和它的新父母做比较。这种交换一直持续到K不大于它的最后一个字母,或者是达到了树的根为止(图6.12是一个图示)。在这个算法中,我们也可以把一个空节点向上筛选,直到达到合适的位置,才把K的值赋给它。11例:小顶堆13273849657650979727384965765013输出:1327493897
6、65765013输出:139749382765765013输出:13 273849502765769713输出:13 276549502738769713输出:13 27 38124965502738769713输出:13 27 387665502738499713输出:13 27 38 495065762738499713输出:13 27 38 499765762738495013输出:13 27 38 49 506597762738495013输出:13 27 38 49 509765762738495013输出:13 27 38 49 50 65137665972738495013输出:
7、13 27 38 49 50 659765762738495013输出:13 27 38 49 50 65 769765762738495013输出:13 27 38 49 50 65 76 97算法HEAPBOTTOMUP/用自底向上算法,从给定数组的元素中构造一个堆/输入:一个可排序元素的数组H.R1N/输出:一个堆H.R1N VOID HEAPADJUST (HEAPTYPE &H, INT S, INT M) / 已知H.RS.M中记录的关键字除H.RS.KEY之外均满足堆的定义,本函数依据 / 关键字的大小对H.RS进行调整,使H.RS.M成为一个大顶堆(对其中记录的关键字而
8、言) RC = H.RS; / 暂存根结点的记录 FOR ( J=2*S; J=M; J*=2 ) / 沿KEY较大的孩子结点向下筛选 IF ( JM & H.RJ.KEY= H.RJ.KEY ) BREAK; / 不需要调整 H.RS = H.RJ; S = J; / 把大关键字记录往上调 H.RS = RC; / 回移筛选下来的记录 / HEAPADJUST从堆中删除最大的键第一步:根的键和堆的最后一个键K做交换。第二步:堆的规模减1。第三步:严格按照我们在自底向上堆构造算法中的做法,把K沿着树向下筛选,来对这棵树较小的树进行“堆化”。也就是说,验证K是否满足父母优势:如果它满足,
9、我们就完成了;如果不满足,K和它较大的子女做交换;然后重复这个操作,知道K在新位置中满足了父母优势要求为止。删除的效率取决于在交换和堆的规模减1后,树的“堆化”所需的键值比较次数。既然它所需的键值比较次数不可能超过堆的高度的两倍,删除的时间效率也是属于O(的。堆排序堆排序的过程对N个数据的原始无序序列建堆,输出堆顶元素将剩下的N-1个元素调整为堆,输出堆顶元素将剩下的N-2个元素调整为堆,输出堆顶元素.剩下的最后一个元素,本身就是堆堆排序算法VOID HEAPSORT ( HEAPTYPE &H ) CREATEHEAP(H); /建立初始堆 H.R1H.RN; /堆顶元素与最后一个元
10、素交换 FOR(I=N-1; I1; I-) /连续进行堆调节和交换 HEAPADJUST(H); H.R1H.RI; VOID HEAPSORT ( HEAPTYPE &H ) / 对顺序表H进行堆排序。 FOR ( I=H.LENGTH/2; I0; -I ) / 把H.R1.H.LENGTH建成大顶堆 HEAPADJUST ( H, I, H.LENGTH ); W=H.R1 ; H.R1= H.RH.LENGTH; H.RH.LENGTH=W; /交换堆顶和堆底的记录 FOR ( I=H.LENGTH-1; I1; -I ) HEAPADJUST(H, 1, I); / 从根开始调整,将H 重新调整为大顶堆 W=H.R1; H.R1=H.RI; H.RI=W; / 相互交换 堆排序的时
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 丽江云南丽江市交通运输综合行政执法支队执法辅助人员招聘6人笔试历年参考题库及参考答案详解
- 6月安全培训试题及答案
- 《青鸟》题库及答案
- IPMCL-28b-生命科学试剂-MCE
- 2025合同范本无质押、信用借款合同样本
- 2025授权代理合同全面版
- (高清版)DB13∕T 2990.3-2019 毒蘑菇识别 第3部分:3A胃肠炎型毒蘑菇
- 2025全面合同代理合同范本集锦
- 苏教版-常见物质的检验教学设计
- 2025年部分法规适用于商品房买卖合同
- 江苏师范大学《法学导论》2023-2024学年第一学期期末试卷
- 湖北省黄冈、襄阳市2025届高三第二次诊断性检测数学试卷含解析
- 跟着音乐游中国(广州大学)知到智慧树章节答案
- 缺血性肠病病例
- 电大《纳税筹划》考试题库小抄
- 2024年新人教版五年级数学下册《第4单元分数的意义和性质 整 理和复习》教学课件
- 创业人生学习通超星期末考试答案章节答案2024年
- 古诗词诵读《客至》课件+2023-2024学年统编版高中语文选择性必修下册
- 孟母三迁故事绘本课件
- 陕西延长石油集团招聘笔试题库2024
- 集团公司人事检查人力资源检查项目表及评分标准
评论
0/150
提交评论