首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
写一个HeapInsen(R,key)算法,将关键字插入到堆R中,并保证插入后R仍是堆。请分析算法的时间复杂度。提示:将key先插入R中已有元素的尾部(即原堆的长度加1的位置,插入后堆的长度加1),然后自下往上调整,使插入的关键字满足堆性质。
写一个HeapInsen(R,key)算法,将关键字插入到堆R中,并保证插入后R仍是堆。请分析算法的时间复杂度。提示:将key先插入R中已有元素的尾部(即原堆的长度加1的位置,插入后堆的长度加1),然后自下往上调整,使插入的关键字满足堆性质。
admin
2017-01-04
74
问题
写一个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
学硕统考专业
相关试题推荐
马克思为第一国际起草的文件有()。①《共产党宣言》②《临时章程》③《成立宣言》④《资本论》
中国古代史分期问题的焦点有哪些?简述其代表人物及思想。(兰州大学2013年中国史基础真题)
以下选项不属于希腊城邦的形成方式和途径的是()。
共产国际“七大”决定加强各国共产党的自主性,主要是由于()。
“二战”爆发的原因是多种因素综合作用的结果,其中最根本的因素是()。
詹天佑自主设计修建了中国第一条铁路是在()。
假设系统的所有资源是同类型的,系统中的进程每次申请资源数最多1个,那么,下面列出的4种情况中,()可能发生死锁。情况序号系统中进程数资源总量
某模型机的通路结构如下图所示,用寄存器传送语句(如PC→MAR),拟出下列指令从读取到执行的完整流程。(1)数据传送指令MOVX(R0),Y(R1),源和目的操作数地址均采用变址寻址,第1个参数X为源操作数的形式地址,第2个参数为目的操作数的形
若无向图G=(V,E)中含有7个顶点,要保证图G在任何情况下都是连通的,则需要的边数最少是____。
三个进程P1、P2、P3互斥使用一个包含N(N>O)个单元的缓冲区。Pl每次用produce()生成一个正整数并用put()送入缓冲区某一空单元中:P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数;P3每次用getev
随机试题
建筑装饰装修工程计价计算基础多采用()。
()要求市场营销控制工作一定要坚持适度性原则,并保证用于营销控制的费用必须是合理的。
××民营化工企业主要产品为日光油漆。其生产车间和库房中的主要原料和辅料有甲苯、二甲苯、甲基丙烯酸甲酯、丙烯酸丁酯、苯乙烯等。生产车间与库房的耐火等级均为二级,二者间距为10m。原料和产品用机动车运输。另有冬季取暖的燃煤锅炉一台,锅炉房邻近库房一侧,与库房间
下列不计算建筑面积的内容是()。
下列关于违约金的说法,错误的是()。
被评估债券为4年期一次性还本付息债券为10000元,年利率为18%,不计复利,评估时债券的购入时间已满3年,当年的国库券利率为10%,评估人员通过对债券发行企业了解,认为应该考虑2%的风险报酬率,试问该被估债券的评估值最有可能是()元。
共享是中国特色社会主义的本质要求,人人共建,人人共享,是经济社会发展的理想状态,小康不小康,关键看老乡,脱贫攻坚成为“十三五”时期国民经济社会发展的头等大事。阅读材料回答下列问题。材料一:随着宏观经济环境的改变,以区域开发为重点的农村扶贫已经出现
十一届三中全会以来,我党制定的一系列正确的路线、方针、政策促进了我国经济的迅猛发展,这说明()。
小老鼠通过尝试和错误进行的“迷宫”问题解决属于()
若磁盘的写电流波形如图3-5所示。其中①波形的记录方式是(1);②波形的记录方式是(2)。
最新回复
(
0
)