首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
写一个HeapInsen(R,key)算法,将关键字插入到堆R中,并保证插入后R仍是堆。请分析算法的时间复杂度。提示:将key先插入R中已有元素的尾部(即原堆的长度加1的位置,插入后堆的长度加1),然后自下往上调整,使插入的关键字满足堆性质。
写一个HeapInsen(R,key)算法,将关键字插入到堆R中,并保证插入后R仍是堆。请分析算法的时间复杂度。提示:将key先插入R中已有元素的尾部(即原堆的长度加1的位置,插入后堆的长度加1),然后自下往上调整,使插入的关键字满足堆性质。
admin
2017-01-04
29
问题
写一个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
学硕统考专业
相关试题推荐
1824~1828年分别用不同的无机物通过不同的途径合成了同一种有机物——尿素,证明了化学定律对有机物和无机物是同样适用的科学家是()。
试述卡德纳斯改革的背景、内容、性质及意义。
关于希腊古风时代和古典时代的叙述不正确的是()。
隋唐科举制的进士科最先出现在()。
1940年毛泽东的《新民主主义论》:“而所谓民主主义,现在已不是旧范畴的民主主义,已不是日民主主义,而是新范畴的民主主义,而是新民主主义”。毛泽东分民主革命的两个阶段主要依据是
设磁盘的扇区大小为4KB,磁盘转速为15000r/min,磁盘平均寻道时间为4ms,最大数据传输速率为40MB/s,磁盘控制器开销时问为1ms,计算读写一个扇区所需平均时间(不考虑I/O请求队列中的等待时间)。
设计一个算法求图的中心点。设v是有向图G的一个顶点,把v的偏心度定义为:MAX{从w到v的最短距离|w属于V(G))如果v是有向图G中具有的最小偏心度的顶点,则称顶点v是G的中心点。
高度为4的4阶B树最多可容纳()个关键字(根是第1层)。
将两个长度为N的有序表归并到一个长度为2N的有序表,最少需要比较的次数是(),最多需要比较的次数是()。
快速排序最易发挥其长处的情况是()。
随机试题
Internet所采用的远程登录服务协议为()。
EDI软件的重要特征有
铅中毒所致精神障碍的治疗药物不包括
临床上用于解救吗啡类急性中毒引起的呼吸抑制的药物是( )。
环境容量是指对一定地区,根据其(),在特定的产业结构和污染源分布的条件下,为达到环境目标值,所允许的污染物最大排放量。
基本建立现代企业制度的特大型企业集团,投资建设《政府核准的投资项目目录》内的项目,可按项目单独申报核准,也可编制()。
以下哪个会议制定了抗日民族统一战线?()
WorldWarIIwasthewatershedeventforhighereducationinmodernWesternsocieties.【F1】Thosesocietiescameoutofthewarwi
对管理信息系统的结构描述一般可以从横向(基于职能)和纵向(基于管理层次)两个方面来描述。“人员结构安排”是哪个职能哪个管理层次的管理信息系统的任务?
Whenyouhavetomeetsomeonefromadifferentculture,beprepared.Ifyouunderstandculturaldifferences,you’llbeabetter【
最新回复
(
0
)