在O(lgn)时间内修改堆

Question

我一直试图解决这个问题几天了.我在学校遇到以下问题:

设A是一个小堆.操作HEAP-MODIFY(A,i,k)将节点i中的密钥更改为新值k,然后重新排列最小堆中的元素.为O元素最小堆提供在O(lgn)时间内运行的HEAPMODIFY的实现.

由于我们必须设计一个在O(lg(n))时间内运行的算法,我知道我不能只迭代每个元素.我有以下解决方案,但我不确定它是否正确.

HEAP-MODIFY(A,i,k):
    A[i] = K

    if A[i] < A[i/2]
        while A[i] < A[i/2] and i > 1
            exchange A[i], A[i/2]
            i=i/2
    else if A[i] > A[2*i]
    while A[i] > A[2*1] and i <k
        exchange A[i], A[2*i]
        i = 2*1

有关如何解决这个问题的任何建议？

Answer 1

HEAP-MODIFY(A,i,K) 
A[i] = K 
MIN-HEAPIFY(A,1)

我也在研究这个问题，并得到了这个。我和你一样困惑，但我觉得你上面的代码过于复杂。