首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
写一个HeapInsen(R,key)算法,将关键字插入到堆R中,并保证插入后R仍是堆。请分析算法的时间复杂度。提示:将key先插入R中已有元素的尾部(即原堆的长度加1的位置,插入后堆的长度加1),然后自下往上调整,使插入的关键字满足堆性质。
写一个HeapInsen(R,key)算法,将关键字插入到堆R中,并保证插入后R仍是堆。请分析算法的时间复杂度。提示:将key先插入R中已有元素的尾部(即原堆的长度加1的位置,插入后堆的长度加1),然后自下往上调整,使插入的关键字满足堆性质。
admin
2017-01-04
78
问题
写一个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
学硕统考专业
相关试题推荐
1837年倡导用无机肥料来补充土壤中耗去的化学元素的化学家是()。
著名的绥靖政策文件《霍尔—赖伐尔协定》是英、法与意大利签订的,密谋发动()。
明太祖洪武年间与科举制相关的一次大案是()。
隋唐科举制的进士科最先出现在()。
西汉的主要赋税形式中。征收对象是儿童的是()。
材料1942年5月,毛泽东指出,对于革命的文艺家,暴露的对象,只能是侵略者、剥削者、压迫者及其在人民中所遗留的恶劣影响,而不能是人民大众。人民大众也是有缺点的,这些缺点应当用人民内部的批评和自我批评来克服。1955年5月,毛泽东在《驳“舆论一律”
一个TCP连接总是以1KB的最大段发送TCP段,发送方有足够多的数据要发送。当拥塞窗口为16KB时发生了超时,如果接下来的4个RTT(往返时间)时间内的TCP段的传输都是成功的,那么当第4个RTT时间内发送的所有TCP段都得到肯定应答时,拥塞窗口大小是
某计算机采用Cache一主存一磁盘三级存储系统。Cache的访问时间为t1ns,命中率为p1;若Cache未命中,CPU需直接访问主存,访问时间为t2ns,主存命中率为p2;若所需数据字不在主存中,则访问主存未命中、将包含所需数据字的磁盘数据块装入主存共需
在一个双链表中,在*p结点之前插入*q结点的操作是()。
一台模型机共有7条指令,主频25MHz,各指令的使用频率与CPI如下表所示,该机有8位和16位两种指令字长,采用2—4扩展操作码。8位字长指令为寄存器一寄存器(R—R)二地址类型,16位字长指令为寄存器~存储器(R—M)二地址变址类型(地址码范围在一12
随机试题
试述谈判时提问的时机及要诀。
引起术后伤口裂开的原因有
工程施工质量不符合要求时,经返工重做或更换器具、设备的检验批应( )。
巴塞尔委员会正式发布的第三版巴塞尔协议(巴塞尔协议Ⅲ),确立了银行资本监管新标杆和新高度,使商业银行风险管理的模式发生了本质变化的时间为()
摩擦性失业主要是由()产生的。
头脑风暴法是由()首先提出。
在VisualFoxPro中,表的备注文件的扩展名是______。
ADULATION:
Navigationcomputers,nowsoldbymostcarmakers,cost$2000andup.Nosurprise,then,thattheyaremostoftenfoundinluxur
HollywoodForsakesHistoryforEventsA)OprahWinfreycallsBelovedtheblackequivalentofSchindler’sList.Tobesure,every
最新回复
(
0
)