首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
写一个HeapInsert(R,key)算法,将关键字插入到堆R中,并保证插入后R仍是堆。请分析算法的时间复杂度。提示:将key先插入R中已有元素的尾部(即原堆的长度加1的位置,插入后堆的长度加1),然后自下往上调整,使插入的关键字满足堆性质。
写一个HeapInsert(R,key)算法,将关键字插入到堆R中,并保证插入后R仍是堆。请分析算法的时间复杂度。提示:将key先插入R中已有元素的尾部(即原堆的长度加1的位置,插入后堆的长度加1),然后自下往上调整,使插入的关键字满足堆性质。
admin
2023-02-06
91
问题
写一个HeapInsert(R,key)算法,将关键字插入到堆R中,并保证插入后R仍是堆。请分析算法的时间复杂度。提示:将key先插入R中已有元素的尾部(即原堆的长度加1的位置,插入后堆的长度加1),然后自下往上调整,使插入的关键字满足堆性质。
选项
答案
算法如下: [*] 设该堆对应的树高为h,则满足h≤log
2
R.len,调整是自底向上查找,最多查找到树根,所以时间复杂度为O(log
2
R.len)。
解析
转载请注明原文地址:https://kaotiyun.com/show/bEwD777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
小唯很喜欢地理这门学科,他利用暑假走访了市内多个图书馆,根据地理课所学的知识制作了一张精美的本市手绘地图并附上气候变化特点和地形分析。开学后,小唯主动把这张地图交给地理老师,但老师反应很冷淡。地理老师认为考试不会考本市的地理气候特征,与其花大量时间制作一张
“没有查出病就是健康”实质上忽视了人的心理健康。()
布鲁纳认为不论教师教什么学科,务必使学生理解该学科的基本结构。依此而建立的课程理论是()。
“侧耳聆听”“举目凝视”“屏息凝视”等现象反映出注意的()。
一位老师认为,儿童就像一张白纸,如果给他足够的时间和资源,他能将儿童培养成任何你想要其成为的人。这位老师的观点与教育学家()的教育主张相似。
某商场为了促销,进行掷飞镖游戏。每位参与人员投掷一次,假设掷出的飞镖均扎在飞镖板上且位置完全随机,扎中中间阴影部分区域(含边线)即为中奖。该商场预设中奖概率约为60%,仅考虑中奖概率的前提下,以下四幅图形(图中的正三角形和正方形均与圆外切或内接)最适合作为
根据以下资料,回答问题。截至2019年12月31日,中国共产党党员总数为9191.6万名,同比增长1.46%。在党员的性别、民族和学历上,女党员2559.9万名,少数民族党员680.3万名,大专及以上学历党员4661.5万名。在党员的入党时间上,新中国成
音爆是飞行器在突破音障时,由于对空气的压缩无法迅速传播,会逐渐形成激波面,激波面上高度集中的声学能量引起巨大响声,让人耳感受到短暂而极其强烈的爆炸声。音爆只有在突破音障即超音速飞行时才会产生。音爆云则是以飞行器为中心轴、从机翼前段开始向四周均匀扩散的圆锥状
过滤气泡是指以大数据与算法推荐为底层架构,根据用户的使用时间、地区以及浏览习惯生成用户画像,并通过算法技术为其呈现独一无二的界面体验。网络上这种针对个人化搜索而提供筛选后结果的推荐算法,被称为过滤气泡。根据上述定义,下列不属于过滤气泡的是:
一只闹钟的秒针顶点距离表盘圆心4厘米,分针顶点距离表盘圆心3厘米。小王烧开一壶水的时间内,秒针顶点累计移动了40厘米。那么这一时间段内,分针顶点与表盘圆心的连线扫过的扇形面积为多少平方厘米?
随机试题
宫颈癌最常见的为子宫内膜癌最常见的为
淋病的潜伏期为( )。
取得执业资格后,超过规定时限未申请注册的人员必须(),才能注册。
在绘制现金流量图时,应把握的要素有现金流量的()。
一般认为,长期供给曲线的弹性要比短期供给曲线的弹性()。
一、注意事项1.本次申论考试是对应考者阅读理解能力、综合分析能力、提出和解决问题能力、写作能力和文字表达能力的综合测试。2.请使用简体汉字作答。二、给定资料1.据全球最大财经信息供应商汤森路透集团(Reuters)发表的报告称,
宋代诗人秦观在河南汝阳任职时,由于处理政事劳累过度,加上脾胃不调,出现了厌食、胸闷、恶心等症状。虽请当地名医诊治,吃了无数汤药,仍未见好转。一朋友获悉,送来一幅古画,并对他说:你是劳神过度所致,这是王维的《辋川图》,你只要每天凝神细观就能痊愈。秦观于是日日
Foryearsthegirlhadharboredher_____againstherstepmother.Today,shefinallygotthecouragetospeakitout.
LikeJupiter,Saturnisalarge,gaseousplanetcomposed______ofhydrogenandhelium.
DearDigitalDiary—LifeloggingintheInternetAgeFromsleepingandeatingtoexerciseandtravel,technologynowallowsus
最新回复
(
0
)