A-A+

若有N个元素已构成一个小根堆那么如果增加一个元素为Kn+1 请用文字简要说明如何在log2

2022-08-12 15:59:42 问答库阅读 196 次

问题详情

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

请帮忙给出正确答案和分析，谢谢！

参考答案

正确答案：K₁～K_n是堆在K_n+1加入后将K₁．．K_n+1调成堆。设c=n+1f=[c／2]若k_f≤K_c则调整完成。否则k_f与K_c交换之后c=ff=[c／2]继续比较k_f≤K_c或f=0即为根结点调整结束。
K1～Kn是堆,在Kn+1加入后,将K1．．Kn+1调成堆。设c=n+1,f=[c／2],若kf≤Kc,则调整完成。否则,kf与Kc交换之后,c=f,f=[c／2],继续比较,kf≤Kc,或f=0,即为根结点,调整结束。