首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
最小最大堆(min max Heap)是一种特定的堆,其最小层和最大层交替出现,根总是处于最小层。最小最大堆中的任一结点的关键字值总是在以它为根的子树中的所有元素中最小(或最大)。如图所示为一最小最大堆。 编写一算法实现最小最大堆的插入功能。假定最小最
最小最大堆(min max Heap)是一种特定的堆,其最小层和最大层交替出现,根总是处于最小层。最小最大堆中的任一结点的关键字值总是在以它为根的子树中的所有元素中最小(或最大)。如图所示为一最小最大堆。 编写一算法实现最小最大堆的插入功能。假定最小最
admin
2019-08-15
22
问题
最小最大堆(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://jikaoti.com/ti/mMGjFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
二里头文化是我国考古史上的重大发现,具有重大的意义。根据所学知识,回答问题:二里头文化在类型上可以分为()
西周的分封制相当发达,是西周的重要政治制度,也是西周历史的一个显著特点。根据所学知识,回答问题在武王灭商和周公东征的过程中立有大功,或与周有世代同盟关系的异姓贵族也被分封去建立诸侯国家,继续为周王室效力,下列国家:①齐②鲁③燕④宋,属于异姓诸侯国的是(
以下()协议完成了从网卡到IP地址的映射。
路由器采用()方式来发送IP分组。
给定单链表的结点结构typedefstructnode*link;structnode{intitem,linknext;);将两个升序单链表归并为一个升序单链表。
通常通信信道的带宽越大,在数据传输中失真将会()。
一台主机申请了一个到www.ab@C@edu.cn的连接,为了获取服务器的IP地址,首先要进行DNS查询,下图为本次查询的过程,请回答如下问题:(1)由个人主机发送给本地DNS服务器的数据是采用什么传输层协议发送的?利用了哪个端口?(2
某计算机字长16位,采用16位定长指令字结构,部分数据通路结构如下图所示。图中所有控制信号为1时表示有效、为0时表示无效。例如控制信号MDRinE为1表示允许数据从DB打入MDR,MDRin为1表示允许数据从内总线打入MDR。假设MAR的输出一直处于使能状
进程从运行状态转换为就绪状态的可能原因是()。
快速排序算法中,如何选取一个界值(又称为轴元素),影响着快速排序的效率,而且界值也并不一定是被排序序列中的一个元素。例如,我们可以用被排序序列中所有元素的平均值作为界值。编写算法实现以平均值为界值的快速排序方法。
随机试题
在Word2010编辑状态下,当快速工具栏中“剪贴”和“复制”按钮呈灰色显示表示()
医学图像国际通用的通讯、传输标准是
女性,2岁,因腹泻3月余入院,患儿近3个月来,泄泻不止,食入即泻,粪质清稀,完谷不化,有时脱肛,形寒肢冷,面色白,精神萎靡,寐时露睛,舌淡苔白,脉象微细。治法是
下列关于解热镇痛药的使用叙述错误的是
3岁患儿,诊断为猩红热,为防止疾病传播,该患儿应隔离至
甲素知乙家有钱,且每天白天只有一老妇看家,遂起抢劫意念。为使抢劫顺利,甲先盗窃军用手枪1支,子弹10发。一切准备就绪后,将枪弹藏于身上,来到乙家。时逢老妇偶然外出,甲撬门入室,发现室内无人,于是窃得现金及其他财物总价值1万余元。正准备逃离时,老妇回来,甲遂
污水水质的复杂程度,按( )划分为复杂、中等、简单三类。
以下关于铲运机施工工艺的表述正确的是( )。
建筑物及其附属设施的专项维修资金,属于()共有。
forewarnedisforearmed
最新回复
(
0
)