首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
最小最大堆(min max Heap)是一种特定的堆,其最小层和最大层交替出现,根总是处于最小层。最小最大堆中的任一结点的关键字值总是在以它为根的子树中的所有元素中最小(或最大)。如图所示为一最小最大堆。 编写一算法实现最小最大堆的插入功能。假定最小最
最小最大堆(min max Heap)是一种特定的堆,其最小层和最大层交替出现,根总是处于最小层。最小最大堆中的任一结点的关键字值总是在以它为根的子树中的所有元素中最小(或最大)。如图所示为一最小最大堆。 编写一算法实现最小最大堆的插入功能。假定最小最
admin
2019-08-15
46
问题
最小最大堆(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
学硕统考专业
相关试题推荐
明清时期专制主义空前加强,据此回答问题:清代在散文方面,声势最大、影响最广的是桐城派,不属于该派的是()
(1)根据无类IP地址的规则,每个网段中有两个地址是不分配的:主机号全0表示网络地址,主机号全1表示广播地址。因此8位主机号所能表示的主机数就是28-2,即254台。该网络要划分为两个子网,每个子网要120台主机,因此主机位数X应该满足下面三个条件:
就绪队列中有n个进程等待使用一个CPU,那么,如果采用不同的调用算法,就有()种调度顺序。
某计算机的CPU主频为500MHz,CPI为5(即执行每条指令平均需5个时钟周期)。假定某外设的数据传输率为0.5MB/s,采用中断方式与主机进行数据传送,以32位为传输单位,对应的中断服务程序包含18条指令,中断服务的其他开销相当于2条指令的执行时间
如图所示一台路由器连接3个以太网。请根据图中给出的参数回答如下问题:(1)该TCP/IP网络使用的是哪一类IP地址?(2)写出该网络划分子网后所采用的子网掩码。(3)系统管理员将计算机D和E按照图中所示结构连入网络并使用所分配的地址对TC
设某系统有两种磁盘配置:一种单磁盘结构,一种4磁盘组阵列结构。每个磁盘每磁道64个扇区,每扇区1024.字节,转速为10000rpm。找道时间为6ms。两种结构的磁盘控制器每次访问的延迟时间均为1ms。设I/O系统的性能只与磁盘和控制器有关,单磁
若线性表最常用的运算是查找第i个元素及其前驱的值,则采用()存储方式节省时间。
描述滑动窗口机制及其作用。比较停止一等待协议,多帧滑动窗口和后退N帧协议,多帧滑动窗口与选择重传协议的区别。
某路由器的IP地址是125.45.23.12,它在以太网上的物理地址为2345AB4F67CD,它收到了一个分组,分组中的目的IP地址是125.11.78.10。(1)试给出这个路由器发出的ARP请求分组中的各项目。假定不划分子网。
假设有一个进程拥有两个线程(编号为0和1)需要去访问同一个共享资源,为了避免竞争状态的问题,必须实现一种互斥机制,使得在任何时候只能有一个线程在访问这个资源。假设有如下的一段代码:intflagL22;/*flag数组,初始化为FALSE*/
随机试题
铣削六角棱柱,其侧棱之间和侧面之间的夹角是相等的,用分度头简单分度法进行分度。()
Thepopulationoftheworldisgrowingatadangerous______.
房颤发生的心外原因首先考虑
宏盛机械进出口公司(2102911013)从香港进口一批无接头电缆,该批商品属于法定检验检疫和自动进口许可管理商品。货物于2005年10月11日在香港装船,于2006年3月5日在天津港入境。宏盛机械进出口公司委托天津某报关公司于次日向海关申报进口。
下列关于持有期货公司股权的表述,正确的有()。
下列选项中不属于信贷人员分析客户的技术水平的是()
根据企业所得税法律制度的规定,纳税人取得的下列收入,应计入应纳税所得额的有()。
家长应根据儿童的年龄特点选择玩具,一岁前儿童玩具主要是()。
伴随着现今的天文科普之热,是否也应带给其他专业的科普工作者一些启示?比如,要让大众真正了解一个学科,除了灌输知识为主的讲座、海报,能否试试另一种“人文路线”,讲讲学科中体现出的自然之美、人类探索精神之美?当然更重要的,是培养一支愿意全情投入的科普工作者队伍
2006年至2011年全年我国农村居民人均纯收入分别为3587元、4140元、4761元、5153元、5919元、6977元;城镇居民人均可支配收入分别为11759元、13786元、15781元、17175元、19109元、21810元。20
最新回复
(
0
)