首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
最小最大堆(min max Heap)是一种特定的堆,其最小层和最大层交替出现,根总是处于最小层。最小最大堆中的任一结点的关键字值总是在以它为根的子树中的所有元素中最小(或最大)。如图所示为一最小最大堆。 编写一算法实现最小最大堆的插入功能。假定最小最
最小最大堆(min max Heap)是一种特定的堆,其最小层和最大层交替出现,根总是处于最小层。最小最大堆中的任一结点的关键字值总是在以它为根的子树中的所有元素中最小(或最大)。如图所示为一最小最大堆。 编写一算法实现最小最大堆的插入功能。假定最小最
admin
2019-08-15
27
问题
最小最大堆(min max Heap)是一种特定的堆,其最小层和最大层交替出现,根总是处于最小层。最小最大堆中的任一结点的关键字值总是在以它为根的子树中的所有元素中最小(或最大)。如图所示为一最小最大堆。
编写一算法实现最小最大堆的插入功能。假定最小最大堆存放在数组中,关键字为整数。
选项
答案
从插入位置进行调整,调整过程由下到上。首先根据元素个数求出插入元素所在层次数,以确定其插入层是最大层还是最小层。若插入元素在最大层,则先比较插入元素是否比双亲小,如是,则先交换,之后,将小堆与祖先调堆,直到满足小堆定义或到达根结点;若插入元素不小于双亲,则调大堆,直到满足大堆定义。若插入结点在最小层,则先比较插入元素是否比双亲大,如是,则先交换,之后,将大堆与祖先调堆;若插入结点在最小层且小于双亲,则将小堆与祖先调堆,直到满足小堆定义或到达根结点。 void MinMaxHeapIns(RecType R[ ],int n){ //假设R[1..n—1]是最小最大堆,插入第n个元素,把R[1..n]调成最小最大堆 j=n;R[0]=R[j]; h=log
2
n+l: //求高度 if(h%2==0){ //插入元素在偶数层,是最大层 i=n/2: if(R[0].key<R[i].key){ //插入元素小于双亲,先与双亲交换,然后调小堆 R[j]=R[i]; j=i/4; while(j>0&&R[j]>R[i]){ R[i]=R[j];i=j;j=i/4;} //调小堆 R[i]=R[0]; } else{ //插入元素大于双亲,调大堆 i=n;j=i/4; while(j>0&&R[j]<R[i]){R[i]=R[1];i=j;j=i/4;} R[i]=R[0]; } } else{ //插入元素在奇数层,是最小层 i=n/2; if(R[0].key>R[i].key){ //插入元素大于双亲,先与双亲交换,然后调大堆 R[J]=R[i]; j=i/4; while(j>0&&R[j]<R[i]){ R[i]=R[j];i=j;j=i/4; } //调大堆 R[i]=R[0]; } else{ //插入元素小于双亲,调小堆 i=n;J=i/4; while(j>0&&R[j]>R[i]){ R[i]=R[j];i=j;j=i/4;} R[i]=R[0]; } } }
解析
转载请注明原文地址:https://kaotiyun.com/show/FKCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
卡诺莎事件
(1)页面长度为1KB=210B,因此页内偏移地址占10位。主存大小为16KB=214B,所以物理地址占14位。0AC5H=0000101011000101B,除去后10位,得到页号为2,则查找页表可知物理块号为4,所以物理地址是0100101100
三个进程P1、P2、P3互斥使用一个包含N(N>O)个单元的缓冲区。P1每次用produce()生成一个正整数并用put()送入缓冲区某一空单元中;P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数;P3每次用getev
某机字长32位,它的存储容量为256MB,按字节编址,则它的寻址范围大小为()。
一个UDP用户的数据报的数据部分长为8192字节。那么通过以太网来传播该UDP数据报时,最后一个IP分片的数据长度是()。
下列几种排序方法中,要求内存量最大的是()。
一个SPOOUNG系统由输入进程I、用户进程P、输出进程O、输入缓冲区、输出缓冲区组成。进程I通过输入缓冲区为进程P输入数据,进程P的处理结果通过输出缓冲区交给进程O输出。进程间数据交换以等长度的数据块为单位,这些数据块均存储在同一个磁盘上,因此,SPOO
下面关于进程的叙述中,正确的是()。
有一个仓库,可以存放A和B两种产品,但要求:(1)每次只能存入一种产品(A或B);(2)-N<A产品的数量-B产品的数量<M。其中,N和M是正整数。试用P,V操作描述产品A与产品B的入库过程。
随机试题
肾图检查常用的示踪剂是
A.益气补虚B.扶正祛邪C.缓峻护正D.化痰止咳E.调和诸药麻黄汤中配伍炙甘草的主要用意是
对于生活垃圾卫生填埋的黏土覆盖结构,自上而下布置,()是符合《生活垃圾卫生填埋技术规范》(CJJ17—2004,J302—2004)要求的。
城市空间环境演进的基本规律不包括()。
期货公司的股东及实际控制人决定转让所持有的期货公司股权,应当在3日内通知期货公司。()
财政补贴与社会保障支出的区别主要体现于()。
(2016年)甲公司注册于某市东城区。2014年有关收支情况如下:(1)取得产品销售收入2000万元、国债利息收入30万元、接受捐赠收入10万元。(2)缴纳工商行政罚款2万元、税收滞纳金1万元。(3)缴纳增值税200万元、城市维护建设税和教育费
投射作用,是指个体将自己不喜欢或不能承受但又是自己具有的冲动、动机、态度和行为转移到他人或周围事物上,认为他人或周围事物也有这样的动机和行为。根据上述定义,下列不属于投射作用范畴的一项是:
已知f(1)=0,则
ThehomelessmakeupagrowingpercentageofAmerica’spopulation.【C1】______,homelessnesshasreachedsuchproportionsthatlo
最新回复
(
0
)