首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
写一个HeapInsen(R,key)算法,将关键字插入到堆R中,并保证插入后R仍是堆。请分析算法的时间复杂度。提示:将key先插入R中已有元素的尾部(即原堆的长度加1的位置,插入后堆的长度加1),然后自下往上调整,使插入的关键字满足堆性质。
写一个HeapInsen(R,key)算法,将关键字插入到堆R中,并保证插入后R仍是堆。请分析算法的时间复杂度。提示:将key先插入R中已有元素的尾部(即原堆的长度加1的位置,插入后堆的长度加1),然后自下往上调整,使插入的关键字满足堆性质。
admin
2017-01-04
58
问题
写一个HeapInsen(R,key)算法,将关键字插入到堆R中,并保证插入后R仍是堆。请分析算法的时间复杂度。提示:将key先插入R中已有元素的尾部(即原堆的长度加1的位置,插入后堆的长度加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.len].key=key; //增加新值到原堆中已有元素的尾部且堆的长度加1 i=R.1en/2;j=R.len; while(i>0){ //调整为堆 if(R.Rec[i].key<R.Rec[j].key){ R.Rec[0]=R.Rec[i];R.Rec[i]=R.Rec[j];R.Rec[i]=R.Rec[0]; } j=i;i=i/2; //继续自底向上查找 } } 设该堆对应的树高为h,则满足h≤log
2
R.len,调整是自底向上查找,最多查找到树根,所以时间复杂度为O(log
2
R.len)。
解析
转载请注明原文地址:https://kaotiyun.com/show/bQRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
1949年,中共召开七届二中全会主要是为了()。
以下不是巴黎和会的主要议题的是()
诸侯国的国君如何用人呢?有人主张:“左右皆曰不可,勿听;诸大夫皆曰不可,勿听;国人皆曰不可,然后察之,见不可焉,然后去之。”这种主张最终可能出自下列哪位思想家之口()。
1920年,苏俄农民中流传着这样的说法:“土地属于我们,面包却属于你们;水属于我们,鱼却属于你们;森林属于我们,木材却属于你们”,它反映的是战时共产主义政策()。
1534年英国议会宣布英国教会断绝与罗马教廷一切关系的文件是()。
阅读材料,回答以下问题:重庆中央党部,暨中央执监委员诸同志均鉴:今年4月,临时全国代表大会宣言,说明此次抗战之原因,曰:“自塘沽协定以来,吾人所以忍辱负重与倭国周旋,无非欲停止军事行动,采用和平方法,先谋北方各省之保全,再进而谋东北四省问题之合理解决,
世界近代史上,世界经济发展经历了两次大的飞跃,即第一次工业革命和第二次工业革命。阅读下面两段材料,回答问题:材料一工业革命的主角——蒸汽机,是经验和科学相结合的产物。科学对工业革命的发展做出重大贡献。工场手工业的生产,主要依靠以人力和经
材料1942年5月,毛泽东指出,对于革命的文艺家,暴露的对象,只能是侵略者、剥削者、压迫者及其在人民中所遗留的恶劣影响,而不能是人民大众。人民大众也是有缺点的,这些缺点应当用人民内部的批评和自我批评来克服。1955年5月,毛泽东在《驳“舆论一律”
下列排序算法中,时间复杂度为O(nlogn)且占用额外空间最少的是()。
一台模型机共有7条指令,主频25MHz,各指令的使用频率与CPI如下表所示,该机有8位和16位两种指令字长,采用2—4扩展操作码。8位字长指令为寄存器一寄存器(R—R)二地址类型,16位字长指令为寄存器~存储器(R—M)二地址变址类型(地址码范围在一12
随机试题
IwouldhaveseenheroffbutI______fullyengagedyesterdaysoIjustsaidgoodbyetoheroverthephone.
铸造支架卡环模截面外形应为A.外圆内平的椭圆形B.外圆内平的半圆形C.长方形D.外尖内平的三角形E.正方形
依据《药品经营质量管理规范》有关规定,有关药品批发企业药品储存说法错误的是
关于审计业务的三方关系人,下列说法中错误的有()。
“吴带当风”“曹衣出水”样式的创造者分别是__________和__________。
在一次体育课上,20名学生进行了箭靶射击测试。随后这些学生上了两天的射箭技能培训课后,又重新进行了测试,结果他们的准确率提高了30%。该结果表明,培训课对于提高人们的射靶准确率是十分有效的。下列哪个选项如果正确,最能支持以上结论?
打开考生文件夹下的演示文稿yswg.pptx,按照下列要求完成对此文稿的修饰并保存。第二张幻灯片版式改为“两栏内容”,将考生文件夹下的图片文件ppt1.jpg插入第二张幻灯片右侧内容区,图片动画设置为“进入”“基本缩放”,效果选项为“缩小”,并插入备注
PASSAGETHREEWhatfeaturedelightstheauthormost?
A.foundB.effectivelyC.stimulantsD.medicineE.anxiousF.muchG.moreH.sentimentallyI.emotionallyJ.drugsK.benefic
【S1】【S5】
最新回复
(
0
)