首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
最小最大堆(min max Heap)是一种特定的堆,其最小层和最大层交替出现,根总是处于最小层。最小最大堆中的任一结点的关键字值总是在以它为根的子树中的所有元素中最小(或最大)。如图所示为一最小最大堆。 编写一算法实现最小最大堆的插入功能。假定最小最
最小最大堆(min max Heap)是一种特定的堆,其最小层和最大层交替出现,根总是处于最小层。最小最大堆中的任一结点的关键字值总是在以它为根的子树中的所有元素中最小(或最大)。如图所示为一最小最大堆。 编写一算法实现最小最大堆的插入功能。假定最小最
admin
2019-08-15
52
问题
最小最大堆(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
学硕统考专业
相关试题推荐
某计算机采用Cache一主存一磁盘三级存储系统。Cache的访问时间为t1ns,命中率为p1;若Cache未命中,CPU需直接访问主存,访问时间为t2ns,主存命中率为p2;若所需数据字不在主存中,则访问主存未命中、将包含所需数据字的磁盘数据块装入主存共需
以数组Data[m+1]作为循环队列SQ的存储空间,front为头指针,rear为队尾指针,则执行出队操作的语句是()。
某网络的拓扑结构由下图所示,其中顶点表示路由器。该网络的路由器采用了链路状态路由算法,在某一时刻各个路由器发送的链路状态如下:A:B(1),D(3)B:A(1),D(1),C(3),E(5)C:B(3),D(1)D:A(3),B(1
若二叉树的前序序列为DABCEFG,中序序列为BACDFGE,则其层次序列为()。
文件系统的主要目的是()。
在下列查找的方法中,平均查找长度与结点个数n无关的查找方法是()。
将要相互通信双方怎样进行建立TCP连接?在TCP报文段的首部中只有端口号而没有IP地址,当TCP将其报文段交给IP层时,IP协议怎样知道目的IP地址呢?为什么把IP地址又称为“虚拟地址”,把TCP连接说成是“虚连接”?假设在建立连接时使用2次握手而非3次握
在一个单处理器系统中,存在3个进程,最多有几个进程处于就绪队列()。
某计算机字长为16位,主存地址空间大小为128KB,按字编址。采用单字长指令格式,指令各字段定义如图B-4所示。转移指令采用相对寻址方式,相对偏移量用补码表示,寻址方式定义见表B-1。请回答下列问题:转移指令的目标地址范围是多少?
随机试题
根据《堤防工程施工规范》(SL260—2014),新筑堤防横断面的地面坡度较陡,施工时应将地面坡度削至缓于()。
在刑罚问题上,霍布斯主张
从生产实践中分化出来专门为改造自然和社会进行准备性和探索性的实践形式是()
下列关于诉讼时效的适用及期间起算点的说法中,正确的有()。(2016年回忆版)
贷款风险预警的程序包括()。[2015年5月真题]
某银行在其发行的一款理财产品的宣传材料写到:“本产品预期最高年化收益××%(上不封顶)”,同时也在材料底端用小字注明了“预期收益率不代表产品的实际收益率”。由于银行已在产品说明书中对风险进行了揭示,因此银行认为不需要在宣传材料中重复提示风险。()
某中型煤矿2003年10月生产原煤6000吨,其中外销5500吨(售价550元/吨)。销售本月生产的选煤100吨(选煤回收率为70%),售价1200元/吨;又用本月生产的80吨选煤支付发电厂电费。当月购进原材料及辅助材料,准于抵扣的进项税额为250000
如何理解“三个代表”重要思想是我们党必须长期坚持的指导思想?
Windows操作系统是一种()操作系统。
信息资源的配置过程呈现3种特性,它们分别是()。
最新回复
(
0
)