1

CLRS 练习：6.5-8

该操作从堆中HEAP-DELETE(A,i)删除节点中的项目。给出一个针对 n 元素最大堆及时运行的实现。iAHEAP-DELETEO(lg 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);
4

4 回答 4

4

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

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

有以下三种情况：

  • x大于其父级
  • x小于其父级
  • x等于其父级

如果x等于它的父级，那很容易——我们什么都不做。

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

如果x大于其父级，我们会遇到您提出的问题。处理这不是太棘手 - 我们只需要比较x它的父级，如果x大于父级，我们交换它们。继续这个过程，直到x不再大于它的父节点或者我们到达根（当x没有父节点时）。

话虽如此，您发布的伪代码对我来说看起来很合适。干得好:)

于 2016-07-15T19:34:31.187 回答
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)
于 2017-08-04T18:44:48.247 回答
1

这是一个更简单的版本，你的最大堆是 A，你想删除 i 位置的元素

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

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

于 2018-02-15T18:47:16.603 回答
0

不确定这是否是一个错字，但看起来你实际上在这里增加了：

A.heapsize-=-1

如果 A 实际上是数组 A 的“属性”，我认为你甚至不能改变它，但我可能是错的。当然，如果它只是你拥有的一些变量，那很好。

除此之外，您的伪代码至少似乎处于正常工作状态。如果它仍然不起作用，也许发布整个代码？

于 2016-07-15T18:56:45.973 回答