6

几天来，我一直试图弄清楚这一点。我对学校有一个问题，说明如下：

设 A 为最小堆。HEAP-MODIFY(A, i, k) 操作将节点 i 中的键更改为新值 k，然后重新排列最小堆中的元素。给出一个在 O(lgn) 时间内运行 n 元素最小堆的 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

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

4

3 回答 3

3

您正在朝着正确的方向思考，但您执行的操作并不能保证结果是最小堆。查看以下堆：

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

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

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

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

于 2011-02-22T02:06:55.920 回答
3

您可以找到并删除 Node(i)，将 Node 的值更改为 k 并将其放回堆中。这不是最有效的方法，但它仍然是 log(n)。优点是它很简单，并且可能会重用您已经实现的操作。

于 2011-02-22T02:19:54.233 回答
1 
HEAP-MODIFY(A,i,K) 
A[i] = K 
MIN-HEAPIFY(A,1)

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

于 2011-02-22T02:29:52.987 回答