首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
最小最大堆(min max Heap)是一种特定的堆,其最小层和最大层交替出现,根总是处于最小层。最小最大堆中的任一结点的关键字值总是在以它为根的子树中的所有元素中最小(或最大)。如图所示为一最小最大堆。 编写一算法实现最小最大堆的插入功能。假定最小最
最小最大堆(min max Heap)是一种特定的堆,其最小层和最大层交替出现,根总是处于最小层。最小最大堆中的任一结点的关键字值总是在以它为根的子树中的所有元素中最小(或最大)。如图所示为一最小最大堆。 编写一算法实现最小最大堆的插入功能。假定最小最
admin
2019-08-01
81
问题
最小最大堆(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
学硕统考专业
相关试题推荐
试述清朝在巩固统一多民族国家方面所做的种种努力。
甲骨文的发现是19世纪20世纪之交中国考古学最重要的发现之一,为重新认识三代的历史与文化奠定了基础,开辟了坦途,可称之为中国文化史的里程碑。根据所学知识回答问题:()选拓龟板,印成(),这成为甲骨文的第一部著录之作,此后,甲骨学逐渐成为
军机处的设置加强了皇权,其最重要的作用是()。
二里头文化是我国考古史上的重大发现,具有重大的意义。根据所学知识,回答问题:二里头文化在类型上可以分为()
下列描述中,属于冯.诺依曼体系结构的特点是()。①采用流水线技术;②指令和数据均以二进制表示;③存储程序并且存储时不区别数据和指令。
某定点机字长8位(含1位符号位),现该机中一个寄存器的内容为43H,则将其算术左移一位、算术右移一位的结果分别为()。
若干个等待访问磁盘者依次要访问的柱面为20,44,40,4,80,12,76,假设每移动一个柱面需要3毫秒时间,移动臂当前位于40号柱面,请按下列算法分别计算为完成上述各次访问总共花费的寻找时间。(1)先来先服务算法;(2)最短寻找时间
在机器数中,正数的符号位用“1”表示的是()。
一台主机申请了一个到www.ab@C@edu.cn的连接,为了获取服务器的IP地址,首先要进行DNS查询,下图为本次查询的过程,请回答如下问题:(1)由个人主机发送给本地DNS服务器的数据是采用什么传输层协议发送的?利用了哪个端口?(2
进程和程序的本质区别是()。
随机试题
按照功能划分,沟通可以分为()
某蓄电池厂男工,工龄10年,主诉头昏、头痛、乏力、记忆减退、睡眠障碍、食欲缺乏、脐周隐痛。经检验尿8-ALA为28.6μmol/L。首选的治疗药物是
下列关于药品采购的说法,不正确的是()。
仲裁协议应当具有的内容包括()。
不属于总监理工程师在施工过程中必须下达停工令的情况为()
与生产预算有直接联系的预算包括()。
南湖绿茶协会经国家工商行政管理局商标局核准,于2011年7月2日取得第912××××号“南湖绿茶”注册商标的专用权,商标性质为地理标志证明商标,注册有效期限至2021年7月1日。核定使用的商品为第30类:茶叶。2013年6月,“南湖绿茶”被国家工商行政管理
对于向居民供热并向居民收取彩暖费的供热企业,下列税收免税的有()。
下列各句中,加点词语使用恰当的一项是()。
权力的制约和平衡原则是世界许多国家宪法包括我国宪法的重要原则之一,请简述其内涵及局限性。
最新回复
(
0
)