首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
写一个HeapInsen(R,key)算法,将关键字插入到堆尺中,并保证插入后R仍是堆。请分析算法的时间复杂度。提示:将key先插入R中已有元素的尾部(即原堆的长度加l的位置,插入后堆的长度加1),然后自下往上调整,使插入的关键字满足堆性质。
写一个HeapInsen(R,key)算法,将关键字插入到堆尺中,并保证插入后R仍是堆。请分析算法的时间复杂度。提示:将key先插入R中已有元素的尾部(即原堆的长度加l的位置,插入后堆的长度加1),然后自下往上调整,使插入的关键字满足堆性质。
admin
2019-08-15
68
问题
写一个HeapInsen(R,key)算法,将关键字插入到堆尺中,并保证插入后R仍是堆。请分析算法的时间复杂度。提示:将key先插入R中已有元素的尾部(即原堆的长度加l的位置,插入后堆的长度加1),然后自下往上调整,使插入的关键字满足堆性质。
选项
答案
算法如下: typedef struct{ KeyType key; InfoType otherinfo; }RecType; typedef struct{ RecType Rec[MaxNum]; //MaxNum是一个常量 int len; }SeqList; HeapInsert(SeqList R,KeyType key){ int i,j; R.Rec[++R.1en].key=key; //增加新值到原堆中已有元素的尾部且堆的长度加1 i=R.len/2; j=R.1en; while(i>0){ //调整为堆 if(R.Rec[i].key<R.Rec[j].key){ R.Rec[0]=R.Rec[i];R.Ree[i]=R.Rec[j];R.Rec[i]=R.Rec[0]; } j=i;i=i/2; //继续自底向上查找 } } 设该堆对应的树高为h,则满足h≤log
2
R.1en,调整是自底向上查找,最多查找到树根,所以时间复杂度为O(log
2
R.1en)。
解析
转载请注明原文地址:https://kaotiyun.com/show/nKCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
关于一战后构筑的凡尔赛体系,说法不正确的是()。
当甲午中日战争正在进行时,恩格斯就预言:“中日战争意味着古老中国的终结,意味着它的整个经济基础全盘地却是逐渐地革命化。”这里的“革命化”指的是()。
二里头文化是我国考古史上的重大发现,具有重大的意义。根据所学知识,回答问题:对于二里头文化的发现的意义,下列选项表述最准确的是()
隋唐五代时期是中国古代商品经济发展史上的一个重要阶段,种类多,交换规模大,交换方式多。试回答问题:下列关于隋唐钱币的表述,不正确的是()
编写判定给定的二叉树是否是二叉排序树的函数。
某定点机字长8位(含1位符号位),现该机中一个寄存器的内容为43H,则将其算术左移一位、算术右移一位的结果分别为()。
A、1243B、4312C、2134D、3214D图的BFS遍历。D选项,首先访问结点3,与3邻接的结点4、2都未曾访问过,故3后面因该为2、4(或4、2),故D错。
高度为7的AVL树最少有()个结点。
在一个单处理器系统中,存在3个进程,最多有几个进程处于就绪队列()。
假设有一个进程拥有两个线程(编号为0和1)需要去访问同一个共享资源,为了避免竞争状态的问题,必须实现一种互斥机制,使得在任何时候只能有一个线程在访问这个资源。假设有如下的一段代码:intflag[2];/*flag数组,初始化为FALSE*/
随机试题
男孩,4岁。因咳喘2天、气喘加剧半天就诊。体检:体温正常,吸气性呼吸困难,口唇微绀,听诊两肺广泛哮鸣音,心率140次/分。既往有哮喘发作史5次,有过敏史,其母亲亦有哮喘史。应立即采取哪项措施
某电视台实行频道中心制,以频道为单位实施采编、广告等活动,这样划分部门的依据是【】
_______,靡有朝矣。(《诗经.氓》)
诊断急性阑尾炎,有意义的体征是
“寒极生热,热极生寒”体现了阴阳之间的
根据FIDIC条件,承包人应办理工程施工的履约担保,担保人可以是()。
在价格调整公式中,字母A代表的含义为()。
1克盐放入100克水中,盐与盐水的比是1:101。()
TheMarriageContractAmarriageisacontract.Youcaneitherwritethatcontractyourselforchoosebetweentwoprefabricat
A、Theythinkwritershavewealthandfame.B、Theylikewriting.C、Theywanttoenjoyloneness.D、Theyfollowsomeexamples.A因果关
最新回复
(
0
)