首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
写一个HeapInsert(R,key)算法,将关键字插入到堆R中,并保证插入后R仍是堆。请分析算法的时间复杂度。提示:将key先插入R中已有元素的尾部(即原堆的长度加1的位置,插入后堆的长度加1),然后自下往上调整,使插入的关键字满足堆性质。
写一个HeapInsert(R,key)算法,将关键字插入到堆R中,并保证插入后R仍是堆。请分析算法的时间复杂度。提示:将key先插入R中已有元素的尾部(即原堆的长度加1的位置,插入后堆的长度加1),然后自下往上调整,使插入的关键字满足堆性质。
admin
2023-02-06
87
问题
写一个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
学硕统考专业
相关试题推荐
“十年树木,百年树人。”这句话体现了教师劳动的()特点。
教育心理学常用的方法有()。
在学习立体几何的时候,有些学生能够非常迅速地接受并绘制出三维立体图形,而有些学生则要经过很长时间的学习才能慢慢接受。这体现了学生在()方面的差异。
黄老师在教授学生认识热带植物时,首先让学生认识了榕树、椰子树等植物,然后让学生总结这些植物的共同特点,再认识热带植物。这种学习属于()。
探究学习的实施过程包括()阶段。
教师在编写教学目标时,要求学生“概括出《孔乙己》的故事情节”。这属于布卢姆认知目标中的()。
截至2019年12月31日,中国共产党党员总数为9191.6万名,同比增长1.46%。在党员的性别、民族和学历上,女党员2559.9万名,少数民族党员680.3万名,大专及以上学历党员4661.5万名。在党员的入党时间上,新中国成立前入党的17.4万名,新
H市为推动生态园林城市建设,在全市组织了一次植树活动。已知银杏、香樟、雪松三种树分别为2100株、2050株、1900株,现从这三种树中随机选取栽种到新城地区,为保证有一种树总数量为2017株,则至少选取树木的株数是:
有n个结点的二叉树,已知叶结点个数为n0。(1)写出求度为1的结点的个数的nn1的计算公式。(2)若此树是深度为h的完全二叉树,写出n为最小的公式。(3)若二叉树中仅有度为0和度为2的结点,写出求该二叉树结点个数n的公式。
若G是一个具有36条边的非连通无向图(不含自回路和多重边),则图G的结点数至少是()。
随机试题
斜方肌上束的主要功能是()。
妊娠高血压综合征的基本病理变化是()。
患者,男,50岁。突起呼吸困难,咳粉红色泡沫痰,血压25.3/13.3kPa(190/100mmHg)该患者的最佳治疗药物是()
中央处理器的重要作用是运算和显示。()
(操作员:刘主管;账套:101长套;操作日期:2015年1月1日)新增付款条件。付款条件编码:60D付款条件名称:60天到期日期(天):60
甲事业单位为财政全额拨款的事业单位,自2005年起,实行国库集中支付和政府采购制度。经财政部门核准,甲事业单位的10万元以上的物品和服务采购支出实行财政直接支付方式,10万元以下的物品和服务采购支出以及日常零星支出实行财政授权支付方式。甲事业单位需要采购一
历史与现实证明,________。纵观近年来世界各地的纷争,从西亚北非推倒“多米诺骨牌”到美国政府一度停摆,从伦敦、巴尔的摩街头火光冲天的骚乱到极端势力的暴行震惊世界,各国政治危机的相似之处就在于,共识缺失加剧社会裂痕,最终陷入动荡失序。而中国从破除计划经
以下是李丽测量荔枝质量、密度时的若干操作,如下图所示,请你帮助她完成以下实验:测量荔枝质量前,将天平放在水平桌面上,游码移至标尺的______处.
Twofactorsweighheavilyagainsttheeffectivenessofscientificresearchinindustry.Oneisthegeneralatmosphereofsecrecy
A、Itshowsthestructureoftheearth.B、Itleadstonewchanges.C、Itmaynotbetrue.D、Itisanimportantrevolutioninscien
最新回复
(
0
)