已知由n—1个关键字组成的序列(K1，K2，…，Kn—1)是大顶堆，现在增加一个关键字Kn，要求将关键字序列（K1，K2，…，Kn—1，Kn），重新调整为大顶堆。请完成以下要求：说明你所设计算法的时间复杂度。

admin2017-04-28 87

问题已知由n—1个关键字组成的序列(K₁，K₂，…，K_n—1)是大顶堆，现在增加一个关键字K_n，要求将关键字序列（K₁，K₂，…，K_n—1，K_n），重新调整为大顶堆。请完成以下要求：
说明你所设计算法的时间复杂度。

选项

答案时间复杂度分析：在循环当中，我们可以看出每次都是对结点的父母结点进行调整，因此操作次数正好是树的高度，时间复杂度为O (log₂n)。

解析

转载请注明原文地址:https://kaotiyun.com/show/7PRi777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

试述君士坦丁堡的陷落过程及其影响。
开皇三年，隋文帝下令州县官吏根据户籍簿上登记的年龄，来核对本人体貌，以防诈老诈小逃避租役，是为()。
1905年至1907年间，围绕中国究竟是采用革命手段还是改良方式这个问题，革命派与改良派进行论战的舆论阵地是()。
较早提出了代议制政府理论的思想家是()。
林则徐的反英国侵略的策略思想不包括()。
在阿拉伯()统治时期，阿拉伯军队曾与当时中国的唐朝军队发生冲突。
下列选项中，不属于选官制度的是()
16世纪中期，德意志资产阶级迫切要求实现国家的统一，其首要的目的是()。
()是宋代为支付军政费用而筹措的一宗款项。同时又是各地为筹措这项经费而加征的苛捐杂税的总名称
一个使用选择性重传协议的数据链路层协议，如果采用了5位的帧序列号，那么可以选用的最大窗口是()。

随机试题

下列哪种物质存在时，FAD呼吸链不受影响而NADH呼吸链被抑制()。
放在弹簧平台上的物块A，重力为W，作上下往复运动，当经过图4－55所示位置1、0、2时(0为静平衡位置)，平台对A的约芽力分别为p1、p2，p3，它们之间大小的关系为()。
5月19日，某教学楼工程施工现场在混凝土浇筑过程中，发生模板坍塌事故，造成6人死亡、18人受伤，直接经济损失357万元。该教学楼为框架结构，建筑面积11800m2，事故发生的部位是教学楼中部的共享大厅，该大厅是一个高度为16．5m，进深为15m，长边
各级地方人民政府水行政主管部门应当根据本级人民政府的要求，制定本行政区域内水利工程建设特大生产安全事故应急救援预案，并报()备案。
下列关于直接融资的表述，错误的是()。
甲公司2016年12月31日持有的下列资产、负债中，应当在2016年12月31日资产负债表中作为流动性项目列报的有()。
从业人员做到坚持原则，要()。
2016年4月15日是首个全民国家安全教育日，习近平总书记再次强调国家安全是“头等大事”。通过成立一个机构、构建一个法律体系、讲清一个问题、抓牢一个落脚点，“头等大事”得到全面落实。下列有关说法错误的是()。
设f(x)在区间(一∞，+∞)内具有连续的一阶导数，并设f(x)=2∫0xf’(x—t)t2dt+sinx，求f(x)．
Allhisuniformsarestainedwithpaint,sohisjobmusthave______todowithcoat.

最新回复(0)

已知由n—1个关键字组成的序列(K1，K2，…，Kn—1)是大顶堆，现在增加一个关键字Kn，要求将关键字序列（K1，K2，…，Kn—1，Kn），重新调整为大顶堆。请完成以下要求： 说明你所设计算法的时间复杂度。

计算机408

学硕统考专业

试述君士坦丁堡的陷落过程及其影响。

开皇三年，隋文帝下令州县官吏根据户籍簿上登记的年龄，来核对本人体貌，以防诈老诈小逃避租役，是为()。

1905年至1907年间，围绕中国究竟是采用革命手段还是改良方式这个问题，革命派与改良派进行论战的舆论阵地是()。

较早提出了代议制政府理论的思想家是()。

林则徐的反英国侵略的策略思想不包括()。

在阿拉伯()统治时期，阿拉伯军队曾与当时中国的唐朝军队发生冲突。

下列选项中，不属于选官制度的是()

16世纪中期，德意志资产阶级迫切要求实现国家的统一，其首要的目的是()。

()是宋代为支付军政费用而筹措的一宗款项。同时又是各地为筹措这项经费而加征的苛捐杂税的总名称

一个使用选择性重传协议的数据链路层协议，如果采用了5位的帧序列号，那么可以选用的最大窗口是()。

下列哪种物质存在时，FAD呼吸链不受影响而NADH呼吸链被抑制()。

放在弹簧平台上的物块A，重力为W，作上下往复运动，当经过图4－55所示位置1、0、2时(0为静平衡位置)，平台对A的约芽力分别为p1、p2，p3，它们之间大小的关系为()。

各级地方人民政府水行政主管部门应当根据本级人民政府的要求，制定本行政区域内水利工程建设特大生产安全事故应急救援预案，并报()备案。

下列关于直接融资的表述，错误的是()。

甲公司2016年12月31日持有的下列资产、负债中，应当在2016年12月31日资产负债表中作为流动性项目列报的有()。

从业人员做到坚持原则，要()。

2016年4月15日是首个全民国家安全教育日，习近平总书记再次强调国家安全是“头等大事”。通过成立一个机构、构建一个法律体系、讲清一个问题、抓牢一个落脚点，“头等大事”得到全面落实。下列有关说法错误的是()。

设f(x)在区间(一∞，+∞)内具有连续的一阶导数，并设f(x)=2∫0xf’(x—t)t2dt+sinx，求f(x)．

Allhisuniformsarestainedwithpaint,sohisjobmusthave______todowithcoat.

已知由n—1个关键字组成的序列(K1，K2，…，Kn—1)是大顶堆，现在增加一个关键字Kn，要求将关键字序列（K1，K2，…，Kn—1，Kn），重新调整为大顶堆。请完成以下要求：说明你所设计算法的时间复杂度。