首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
写一个HeapInsert(R,key)算法,将关键字插入到堆R中,并保证插入后R仍是堆。请分析算法的时间复杂度。提示:将key先插入R中已有元素的尾部(即原堆的长度加1的位置,插入后堆的长度加1),然后自下往上调整,使插入的关键字满足堆性质。
写一个HeapInsert(R,key)算法,将关键字插入到堆R中,并保证插入后R仍是堆。请分析算法的时间复杂度。提示:将key先插入R中已有元素的尾部(即原堆的长度加1的位置,插入后堆的长度加1),然后自下往上调整,使插入的关键字满足堆性质。
admin
2017-11-14
47
问题
写一个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://jikaoti.com/ti/6DfjFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
景德镇
三大战役的先后顺序是()
1901年6月,发表《立宪法议》,首先提出君主立宪要求的是()。
法国里昂工人起义提出:“我们只有一个口号‘人人自由平等!’”英国宪章运动请愿书提出:“我们竭尽自由人的义务,就应享受自由人的权利。我们要求普遍选举。”这些要求表明()。①带有空想社会主义色彩②当时工人的要求还没有超出资产阶级民主主义的范畴
阅读材料,回答以下问题:重庆中央党部,暨中央执监委员诸同志均鉴:今年4月,临时全国代表大会宣言,说明此次抗战之原因,曰:“自塘沽协定以来,吾人所以忍辱负重与倭国周旋,无非欲停止军事行动,采用和平方法,先谋北方各省之保全,再进而谋东北四省问题之合理解决,
阅读材料,回答以下问题:重庆中央党部,暨中央执监委员诸同志均鉴:今年4月,临时全国代表大会宣言,说明此次抗战之原因,曰:“自塘沽协定以来,吾人所以忍辱负重与倭国周旋,无非欲停止军事行动,采用和平方法,先谋北方各省之保全,再进而谋东北四省问题之合理解决,
希腊雅典城邦的“民众法庭审判官由公民抓签选出,任期只有一年,每个公民一生中只能担任两次审判官的职务”。此规定()。
西周的官僚制度已经相当完备,官僚机构庞杂,职官名目繁多。周王室的官僚机构分为两大系统,分别是()。
假定在一个处理机上执行的操作如下:作业估计服务时间片优先数A103B11C23D14E52这些
某中央处理器的数据通路如图所示。MDR为内存数据寄存器,PC为程序计数器,IR为指令寄存器。所有的单线箭头为控制微命令。(1)请说明图中部件X的名称和功能、寄存器Y的名称和功能。(2)请解释:为什么要设置T暂存器?(3)假定指
随机试题
从企业固定资产周转看,企业固定资产的价值周转特点有()
眼窝凹陷,说明
某男,30岁,右下齿痛,疼痛剧烈,齿龈红肿,无龋齿,身热,舌红,苔薄黄,脉浮数。针灸治疗本病的取穴是()
坐骨棘间径平均是
下列付款方式中不属于汇付的是()。
某公司是一家发展迅速的企业,随着企业发展,公司的组织结构、技术条件等都发生了改变。公司在发展中不仅设立了新的职位,而且原有很多职位的工作内容和任职资格也发生了变化。但公司仍然沿用原有的职位说明书,造成职位说明书严重脱离实际。公司意识到了问题,决定聘请咨询机
张三于2015年6月来到某小城镇创业,当月用25万元购置一套88平方米的普通住房(张三名下没有其他住房),用20万元购置一间60平方米的临街商铺。为满足创业需要,当月他从某工厂用5万元购置了一辆该厂使用过的二手面包车(该厂能提供车购税和车船税完税凭证);从
在物业管理活动中,业主相互之间最本质的关系是()
阅读下面材料,回答问题。春天悄然而至,为让幼儿感受春天赋予我们生活的诗情画意,我(老师)教幼儿学习诗歌《春天的颜色》。在第一次语言活动中,为了激起幼儿的学习兴趣,让幼儿理解诗歌大意,我特别画了几幅有关春天美景的图画。但无论我怎么解释,孩子就是记不住诗句,
α、β是实系数方程χ2+2χ+2=0的两个虚根,则它们在复平面上对应的向量夹角的正弦值为().
最新回复
(
0
)