首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
写一个HeapInsen(R,key)算法,将关键字插入到堆R中,并保证插入后R仍是堆。请分析算法的时间复杂度。提示:将key先插入R中已有元素的尾部(即原堆的长度加1的位置,插入后堆的长度加1),然后自下往上调整,使插入的关键字满足堆性质。
写一个HeapInsen(R,key)算法,将关键字插入到堆R中,并保证插入后R仍是堆。请分析算法的时间复杂度。提示:将key先插入R中已有元素的尾部(即原堆的长度加1的位置,插入后堆的长度加1),然后自下往上调整,使插入的关键字满足堆性质。
admin
2017-01-04
81
问题
写一个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
学硕统考专业
相关试题推荐
二战后国家垄断资本主义发展的主要形式有哪些?
简述魏晋玄学的产生背景及其代表人物的基本思想。(2009年统考真题)
农业革命的中心以及农业革命的影响。
简述近代香港问题的形成。
十六国时期的历史,可以划分为前后两个时期,其分界线是()。
法国里昂工人起义提出:“我们只有一个口号‘人人自由平等!’”英国宪章运动请愿书提出:“我们竭尽自由人的义务,就应享受自由人的权利。我们要求普遍选举。”这些要求表明()。①带有空想社会主义色彩②当时工人的要求还没有超出资产阶级民主主义的范畴
第一个五年计划的具体时间段是()。
操作系统采用页式存储管理方法,要求()。
在因特网中,IP数据报的传输需要经由源主机和中途路由器到达目的主机,下面说法正确的是()。
随机试题
消化性溃疡最常见的病因是幽门螺杆菌和__________。
慢性溃疡性结肠炎活动期的镜下表现不包括:
未经批准擅自开办医疗机构行医的,由卫生行政部门给予的行政处罚是未经批准擅自非法行医,给患者造成损害的,应承担的法律责任是
患者腹大胀满不舒,早宽暮急,面色苍黄,嗜睡,语无伦次,逐渐昏迷,舌苔灰腻,脉弦细而滑。治疗应首选
某男,56岁。遍体浮肿,腹胀,二便不利,服用峻下遂水的舟车丸,为防伤正气,联用的中成药是
必须确保他们的知识、技能和工作是一种高质量,不过时的,有证据基础的并与他们业务领域相关的是应发挥敬业精神,共同促进修订药事法规,以健全医药专业制度是
霍夫兰德(C.Hovland)态度转变模型包含的要素有()。
学习(厂义)
人民警察必须把公安机关的利益作为自己全部工作的出发点和归宿。()
Aboutthisnovel,whichofthefollowingstatementisNOTtrue?Wecandrawfromthepassagethatthe"primitivecharacter"wit
最新回复
(
0
)