首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
写一个HeapInsert(R,key)算法,将关键字插入到堆R中,并保证插入后R仍是堆。请分析算法的时间复杂度。提示:将key先插入R中已有元素的尾部(即原堆的长度加1的位置,插入后堆的长度加1),然后自下往上调整,使插入的关键字满足堆性质。
写一个HeapInsert(R,key)算法,将关键字插入到堆R中,并保证插入后R仍是堆。请分析算法的时间复杂度。提示:将key先插入R中已有元素的尾部(即原堆的长度加1的位置,插入后堆的长度加1),然后自下往上调整,使插入的关键字满足堆性质。
admin
2017-11-14
48
问题
写一个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
学硕统考专业
相关试题推荐
1925年爆发的当时世界上罢工时间最长的一次斗争是()。
为加强君权,皇太极时代开始直接控制的“上三旗”不包括()。
“国际工人协会”宣布成立后,10月协会选出了第一任主席,他是()。
二战期间,下列四次战役的时间先后顺序是()①莫斯科战役②诺曼底登陆③不列颠之战④阿拉曼战役
下列有关《布列斯特和约》的说法中,错误的一项是()。
阅读材料,回答以下问题:一、大清帝国之皇统,万世不易。二、皇帝神圣,不可侵犯。三、皇帝权以宪法规定为限。四、皇帝继承之顺序,于宪法规定之。五、宪法由资政院起草议决,皇帝颁布之。六、宪政改正提案权,属于国会。七、上院议员,由国民于法定特别资格公选之。八、总
简述按照恩格斯的划分方法人类的起源与进化。
试就MutualExclusion、Progress、BoundedWaiting论述以下解决双进程临界区问题的算法是错误的:ProcessPO:do{flag[0]=true;While(flag[1]);
给定序列{3,5,7,9,11,13,15,17),(1)按表中元素的顺序依次插入一棵初始为空的二叉排序树,画出插入完成后的二叉排序树,并求在等概率情况下查找成功的平均查找长度。(2)按表中元素的顺序构造一棵平衡二叉树,并求其在等概率情
某中央处理器的数据通路如图所示。MDR为内存数据寄存器,PC为程序计数器,IR为指令寄存器。所有的单线箭头为控制微命令。(1)请说明图中部件X的名称和功能、寄存器Y的名称和功能。(2)请解释:为什么要设置T暂存器?(3)假定指
随机试题
中共二大宣言规定了中国共产党的最低纲领,其基本内容是()
不与主动脉弓相连的结构是
A.可可豆脂B.十二烷基硫酸钠C.卡波姆D.羊毛脂E.丙二醇常作凝胶基质的是()
在某一抢劫案件的诉讼过程中,犯罪嫌疑人冯某、被害人齐某先后提出回避请求,对于哪一请求有关机关应不予支持?()
某期货公司注册资本5000万元,董事长张某在期货公司里面工作10余年,总经理李某曾经在证券公司里面任职达6年之久,副总经理孙某在期货公司里从事期货业务已满5年,张某、孙某在期货公司里面连续担任董事长、副总经理分别达5年、4年之久,张某已经获得了期货从业人
有限责任公司股东会作出增加公司注册资本的决议时,应当经出席股东会议的全体股东一致通过。()
“人法地,地法天,天法道,道法自然。”一语出自()。
期货经纪机构的职能包括()等。
对于不批准逮捕而又需要继续侦查的,可依法实施()。
旁听生
最新回复
(
0
)