首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
最小最大堆(min max Heap)是一种特定的堆,其最小层和最大层交替出现,根总是处于最小层。最小最大堆中的任一结点的关键字值总是在以它为根的子树中的所有元素中最小(或最大)。如图所示为一最小最大堆。 编写一算法实现最小最大堆的插入功能。假定最小最
最小最大堆(min max Heap)是一种特定的堆,其最小层和最大层交替出现,根总是处于最小层。最小最大堆中的任一结点的关键字值总是在以它为根的子树中的所有元素中最小(或最大)。如图所示为一最小最大堆。 编写一算法实现最小最大堆的插入功能。假定最小最
admin
2019-08-01
89
问题
最小最大堆(min max Heap)是一种特定的堆,其最小层和最大层交替出现,根总是处于最小层。最小最大堆中的任一结点的关键字值总是在以它为根的子树中的所有元素中最小(或最大)。如图所示为一最小最大堆。
编写一算法实现最小最大堆的插入功能。假定最小最大堆存放在数组中,关键字为整数。
选项
答案
从插入位置进行调整,调整过程由下到上。首先根据元素个数求出插入元素所在层次数,以确定其插入层是最大层还是最小层。若插入元素在最大层,则先比较插入元素是否比双亲小,如是,则先交换,之后,将小堆与祖先调堆,直到满足小堆定义或到达根结点;若插入元素不小于双亲,则调大堆,直到满足大堆定义。若插入结点在最小层,则先比较插入元素是否比双亲大,如是,则先交换,之后,将大堆与祖先调堆;若插入结点在最小层且小于双亲,则将小堆与祖先调堆,直到满足小堆定义或到达根结点。 void MinMaxHeaplns(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
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].key){ //插入元素大于双亲,先与双亲交换,然后调大堆 R[j]=R[i]; j=i/4; while(j>0&&R[-j]
0&&R[j]>R[i]){ R[i]=R[j];i=j;j=i/4;} R[i]=R[0]; } } }
解析
转载请注明原文地址:https://kaotiyun.com/show/w3Ci777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
两税法产生的背景、内容是什么?并对其进行评价。
永元四年(公元92年),汉和帝用宦官()掌握的一部分禁军,消灭了窦氏势力。郑众从此参与预政事,并受封为侯,这是宦官用权和封侯的开始。
在欧美资产阶级革命时代,最能体现出资产阶级革命要求的文献是()。
根据1931年的威斯敏斯特法,英国()。
德国纳粹党消灭资产阶级民主制的关键性事件是()。
编写一个算法,实现以较高的效率从有序顺序表A中删除其值在x和y之间x≤A[i]≤y的所有元素。
设二维数组A[6][10],每个数组元素占用4个存储单元,若按行优先顺序存放的数组元素,a[0][O]的存储地址为860,则a[3][5]的存储地址为()。
并发使得处理机的利用率得到提高,其主要原因是处理机与IO可以同时为多个进程服务,也即处理机与IO设备真正地并行。但是处理机的利用率提高并不是简单地将两个进程的处理机利用率相加,而是遵循一定的规律。现在有一个计算机系统采用多道程序技术实现了并发,调度算法采用
网络如图所示。链路旁边注明的数字代表链路的长度(假想单位)。试利用Dijk-stra算法求出从结点A到所有其他结点的最短路由。
试比较脱机I//O和联机I/O。
随机试题
人民法院准许延期提供证据的,被告应当在正当事由消除后()内提供证据。
在实现社会主义的自我发展与完善中要
A.硬膜外出血B.脑栓塞C.椎动脉系统TIAD.蛛网膜下腔出血E.颅内肿瘤患者,男,55岁。看报纸时突感头痛,复视,颈部僵硬,头颅CT示脑池内高密度影,最可能的诊断为
下列有关股骨的叙述,错误的是
肝硬化患者大量腹水时,体位宜采取
采血清标本作肝功能检查,错误的步骤是
心理是人脑对()。
Everyonebecomesalittlemoreforgetfulastheygetolder,butmen’smindsdeclinemorethanwomen’s,accordingtotheresults
改革开放40年来,我国民营经济从小到大、从弱到强,不断发展壮大。截至2017年年底,我国民营企业数量超过2700万家,个体工商户超过6500万户,注册资本超过165万亿元。概括起来说,民营经济具有“五六七八九”的特征,即贡献了50%以上的税收,60%以上的
Whatcandogssee?Theanswertothisquestionisdisappointing;dogs【C1】______seenocolors.Theanswerisdisappointing【C2】___
最新回复
(
0
)