algorithm - 在 O(lgn) 时间内修改堆

Question

这几天我一直在努力解决这个问题。我有一个关于学校的问题，内容如下:

Let A be a min-heap. The operation HEAP-MODIFY(A, i, k) changes the key in the node i to a new value k, then rearranges the elements in a min-heap. Give an implementation of the HEAPMODIFY that runs in O(lgn) time for an n-element min-heap.

由于我们必须设计一个在 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

您的思考方向是正确的，但您执行的操作并不能保证得到最小堆。查看以下堆:

  ..
  11
 /  \
19  63 (<-was 13)
.. /  \
  55  15
  ..  ..

假设您刚刚将 key 13 更新为 63 并且想要恢复最小堆属性。您的代码将交换 55 和 63，因为 55<63，但 55 将是 63 和 15(!) 的父级，因此会损害最小堆属性。

您需要的函数(恢复最小堆属性)称为“heapify”。这不是微不足道的，但也不是很复杂。在这篇关于 heapsort 的维基百科文章中查找其解释.只要您理解而不只是复制，阅读/学习解决方案就没有错。

如果您之后还有疑问，请提出。