从最大堆中删除节点 A[i]

Question

CLRS 练习：6.5-8

操作HEAP-DELETE(A,i) 从堆A 中删除节点i 中的项目。给出 HEAP-DELETE 的实现，它在 O(lg n) 时间内运行 n 元素最大堆。

请问是不是算法错误输入A[10]={84,22,19,21,3,10,6,5,20}（索引从1开始），A[6]=10被删除。用 A[6] 替换最后一个节点会导致违反堆属性，忽略父值。

我为此编写了一个算法，想知道它是否工作正常或者我哪里出错了？

HEAP-DELETE(A,i)
  A[i]=A[A.heapsize]
  A.heapsize-=1
  while i>1 and A[parent(i)]<A[i]
    swap A[i] with A[parent(i)]
    i=parent(i);

Answer 1

不确定是不是打错了，但看起来你实际上是在这里递增的：

A.heapsize-=-1

如果 A 实际上是数组 A 的 "property"，我认为您甚至无法更改它，但我可能是错的。当然，如果它只是你的一些变量，那也没关系。

除此之外，您的伪代码至少看起来可以正常工作。如果仍然无法正常工作，也许 post 整个代码？

Answer 2

从最大堆中删除节点时，我们首先要做的是将目标元素与最后一个元素交换，然后删除最后一个元素。

现在，我们面临着修复最大堆的问题，因为我们刚刚移动了一个元素。让我们将刚刚移动的元素称为 x.

分三种情况：

x 大于其父项
x 小于其父项
x 等于其父

如果 x 等于它的父级，那很简单 - 我们什么都不做。

如果 x 小于它的父级，我们需要做的就是 MAX-HEAPIFY （我假设你从评论中理解它是如何工作的），因为我们需要修复以下任何错误 x.

如果 x 大于其父级，我们运行进入您提出的问题。处理这个并不太棘手——我们只需要将 x 与其父级进行比较，如果 x 大于父级，我们就交换它们。继续此过程，直到 x 不再大于其父项或我们到达根（当 x 没有父项时）。

话虽如此，您发布的伪代码在我看来是正确的。干得漂亮:)

Answer 3

这是伪代码：

HEAP-DELETE(A, i):
  A[i] = A[A.heap-size]
  A.heap-size -= 1
  // Case : 8, 7 3, 5 6 1 2, 4 and delete 1
  while(i > 1 and A[Parent(i)] < a[i])
      swap A[i] with A[parent(i)]
      i = Parent(i)
  // Case : 10, 9 6, 8 7 5 4, 3 and delete 6
  MAX-HEAPIFY(A, i)

Answer 4

这里有一个更简单的版本，你的max-heap是A，你要删除第i个位置的元素

DELETE(A, i)
  HEAP-INCREASE-KEY(A, i, A[0]+1)
  HEAP-EXTRACT-MAX(A)

这是它的工作原理，HEAP-INCREASE-KEY 增加要删除的元素的值以使其大于根，这会将元素带到堆的根，然后调用HEAP-EXTRACT-MAX，从堆中删除（并返回）根（要删除的元素）

从最大堆中删除节点 A[i]

Deleting a node A[i] from a Max-Heap

algorithm

clrs

max-heap