首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
写一个HeapInsert(R,key)算法,将关键字插入到堆R中,并保证插入后R仍是堆。请分析算法的时间复杂度。提示:将key先插入R中已有元素的尾部(即原堆的长度加1的位置,插入后堆的长度加1),然后自下往上调整,使插入的关键字满足堆性质。
写一个HeapInsert(R,key)算法,将关键字插入到堆R中,并保证插入后R仍是堆。请分析算法的时间复杂度。提示:将key先插入R中已有元素的尾部(即原堆的长度加1的位置,插入后堆的长度加1),然后自下往上调整,使插入的关键字满足堆性质。
admin
2017-11-14
69
问题
写一个HeapInsert(R,key)算法,将关键字插入到堆R中,并保证插入后R仍是堆。请分析算法的时间复杂度。提示:将key先插入R中已有元素的尾部(即原堆的长度加1的位置,插入后堆的长度加1),然后自下往上调整,使插入的关键字满足堆性质。
选项
答案
算法如下: typedef struct{ KeyType key; InfoType otherinfo; }RecType; typedef struct{ RecType Rec[MaxNum]; //MaxNum是一个常量 int len; }SeqList; Heaplnsert(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
2R.len,调整是自底向上查找,最多查找到树根,所以时间复杂度 为O(log
2
R.len)。
解析
转载请注明原文地址:https://kaotiyun.com/show/Q3Ri777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
【迈镊尼文明】东北师范大学1999年世界上古史真题
下列有关曲辕犁的表述正确的是()①曲辕犁早在中国汉代即已使用了②曲辕犁在中国出现至少比欧洲早一千多年③我国古代的农业工具和农耕技术曾长期居世界领先地位④处于“蒸汽时代”的欧洲农业技术革新,滞后于同时代工业的发
下面哪部经典是我国最早的官方史书?()
1901年6月,发表《立宪法议》,首先提出君主立宪要求的是()。
阅读下列史料,并回答问题:在琶勒尼斯(注:地名)一役获胜后,他(庇西特拉图)便占领政府,并解除人民武装;现在他已能稳定地握住僭主政权,并且取得那克索斯。以吕格达密斯为统治者。他解除人民武装的方法是这样的:他在塞修斯庙举行了一个武装的阅兵式,同时举行一次民
中古时代实行索贡巡行赋税征收方式的国家是()。
中华人民共和国恢复在联合国合法席位的时间是()。
以数组Data[m+1]作为循环队列SQ的存储空间,front为头指针,rear为队尾指针,则执行出队操作的语句是()。
快速排序最易发挥其长处的情况是()。
采用散列函数H(k)===3XkMOD13并用线性探测开放地址法处理冲突,在数列地址空间[0..12]中对关键字序列22,41,53,46,30,13,1,67,51 (1)构造散列表(画示意图); (2)装填因子;
随机试题
下列哪项不属于神经反射的深反射
人工挖土方工程,土壤系潮湿的黏性土,按土壤分类属二类土(普通土)。测试资料表明,挖1m3需消耗基本工作时间60min,辅助工作时间占工作延续时间2%,准备与结束工作时间占工作延续时间2%,不可避免中断时间占1%,休息时间占20%,则此土方工程的时间定额为
根据《堤防工程施工质量评定与验收规程)SL239—1999的规定,堤防工程竣工前的质量抽检项目和数量由()确定。
按索赔事件的性质分,索赔不包括()。
下列有关不切实可行的表述正确的有()。
Disagreementsamongeconomistsarelegendary,butnotontheissueoffreetrade.Arecentsurveyofprominenteconomistsbothc
阻抗本质上是求助者在心理咨询过程中对( )的抵抗。
符号冲突是指在符号的传播过程中,“发讯人”和“收讯人”由于各自在思想、认识和世界观等方面的不同,对符号的使用和理解存在不同程度的差异,进而造成交流的矛盾或冲突。根据上述定义,下列选项属于符号冲突的是()。
小德意志派
Itisawisefatherthatknowshisownchild,buttodayamancanboosthispaternal(fatherly)wisdom—oratleastconfirmthat
最新回复
(
0
)