首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
最小最大堆(min max Heap)是一种特定的堆,其最小层和最大层交替出现,根总是处于最小层。最小最大堆中的任一结点的关键字值总是在以它为根的子树中的所有元素中最小(或最大)。如图所示为一最小最大堆。 编写一算法实现最小最大堆的插入功能。假定最小最
最小最大堆(min max Heap)是一种特定的堆,其最小层和最大层交替出现,根总是处于最小层。最小最大堆中的任一结点的关键字值总是在以它为根的子树中的所有元素中最小(或最大)。如图所示为一最小最大堆。 编写一算法实现最小最大堆的插入功能。假定最小最
admin
2019-08-15
24
问题
最小最大堆(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
学硕统考专业
相关试题推荐
明清时期专制主义空前加强,据此回答问题:以下关于明朝“废行省、设三司”的措施评价最正确的是()
北宋在统一南方割据势力的过程中特设(),把征南所得的财富统一存放,以作日后恢复幽燕之费。
系统阐明社会主义初级阶段理论是在()。
若干个等待访问磁盘者依次要访问的柱面为20,44,40,4,80,12,76,假设每移动一个柱面需要3毫秒时间,移动臂当前位于40号柱面,请按下列算法分别计算为完成上述各次访问总共花费的寻找时间。(1)先来先服务算法;(2)最短寻找时间
已知散列函数为H(key)=key%11,处理冲突的方法为二次探测法,探测的序列为:1,-1,4,-4,…,j2,-j2(j<=m/2)。当di>0时,Hi=(H(key)+di)%m当di<0时,Hi=(H(key)+di+m)%m散列
相对于单一内核结构,采用微内核结构设计实现操作系统具有诸多好处,但是,()并不是微内核的优势。
某计算机的CPU主频为500MHz,CPI为5(即执行每条指令平均需5个时钟周期)。假定某外设的数据传输率为0.5MB/s,采用中断方式与主机进行数据传送,以32位为传输单位,对应的中断服务程序包含18条指令,中断服务的其他开销相当于2条指令的执行时间
一个SPOOUNG系统由输入进程I、用户进程P、输出进程O、输入缓冲区、输出缓冲区组成。进程I通过输入缓冲区为进程P输入数据,进程P的处理结果通过输出缓冲区交给进程O输出。进程间数据交换以等长度的数据块为单位,这些数据块均存储在同一个磁盘上,因此,SPOO
在请求分页存储管理中,若采用FIFO的页面淘汰算法,当分配的页面数增加时,缺页中断的次数()。
通常通信信道的带宽越大,在数据传输中失真将会()。
随机试题
患者,女,30岁,头痛、发热、呕吐3天入院。查体:T39℃,血压110/80mmHg,瞳孔等大等圆,对光反射存在。颈项强直,心肺无异常发现。腰穿脑脊液检查:稍浑浊,Pandy试验阳性,葡萄糖4.0mmol/L,氯化物128mmol/L,细胞计数45×106
28岁已婚妇女,既往月经周期规律。主诉停经12周时出现阴道流血及腹部紧张感。妇科检查:宫口未开,子宫如婴儿头大,软。两侧附件区均触及约手拳大、囊性、活动良好、无压痛肿物,分泌物陈旧血性,尿妊娠试验阳性。本例双侧附件区肿物最可能的诊断是:
信息分类编码工作的核心是()。
亚当.斯密说过:“如果一个社会的经济发展成果不能真正分流到大众手中,那么它在道义上将是不得人心的,并且有风险的,因为它注定会威胁到社会的稳定。”这句话强调的是()。①公平的收入分配有助于协调人们的利益关系②分配不合理会降低效率,阻碍生产的发展③分
根据文字,回答下面问题在经历了2006年到2007年的持续高速上涨,经历了国家出台的数项严厉的宏观调控政策,特别是货币紧缩政策之后,2008年一季度的房地产市场表现显得格外重要。2008年4月2日,国家发改委公布的数据显示,截至3月20日,
根据《刑事诉讼法》,下列情形中不符合法律规定的是()。
文化经典,是一个民族文化______的集中体现。经过千百年的______,文化经典世代相传而广受赞誉,足以说明其深厚的价值和无可替代的作用。填入划横线部分最恰当的一项是()。
下列春秋战国时期发生的大事按照时间先后顺序排列正确的是()。
自我暴露的程度大致可以分为哪几个水平?()
Morethan30,000driversandpassengerswhositinthefrontofthevehiclesarekilledorseriouslyinjuredeachyear.Ataspe
最新回复
(
0
)