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

admin2017-04-28 76

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

选项

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

解析

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

计算机408

相关试题推荐

随机试题

最新回复(0)