若有N个元素已构成一个小根堆，那么如果增加一个元素为Kn+1，请用文字简要说明如何在log2n的时间内将其重新调整为一个堆。

admin2017-01-04 34

问题若有N个元素已构成一个小根堆，那么如果增加一个元素为K_n+1，请用文字简要说明如何在log₂n的时间内将其重新调整为一个堆。

选项

答案K₁～K_n是堆，在K_n+1加入后，将K₁…k_n+1调成堆。设c=n+1，f=[c／2]，若k_f≤K_c，则调整完成。否则K_f与K_c交换之后，c=f,f=[c／2]，继续比较，直到K_f≤K_c或f=0，即为根结点，调整结束。

解析

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

计算机408

相关试题推荐

随机试题

最新回复(0)