1

(USC CSCI 303 作业 4) 问题 7 (6.5-7)：

该操作从堆中Heap-Delete(A, i)删除节点中的项目。给出一个在O ( lg n ) 时间内运行n元素最大堆的实现。iAHeap-Delete

这是参考解决方案的伪代码和描述：

Heap-Delete(A, i)
    A[i] ↔ A[length(A)] 
    length(A) ← length(A) - 1
    Heapify(A, i)

该算法删除节点处的元素i，并将其替换为最后一个元素。然后算法Heapify从节点运行i。

如果“↔”改为“←”不是更好吗？或者这真的有必要吗？

我从 http://www-scf.usc.edu/~csci303/cs303hw4solutions.pdf得到这个（第 4 页）

4

3 回答 3

2

这不是真的必要。也许目的是返回该元素，在这种情况下，您需要将其存储在某个地方，然后再被覆盖。

于 2013-03-15T09:56:19.740 回答
0

也许这样做是为了Heap-Delete()在执行堆排序期间可以重复调用。在堆排序中，最大的项从堆中取出，存放在堆的最后一项中，堆大小减一。然后堆被重新堆化，然后你继续到下一个最大的项目。当堆大小为 1 时，最终结果是堆所基于的数组从小到大排序。Heap-Delete()以这种方式编写Heap-Sort()可以非常简单：

while (HeapSize>0)
   HeapDelete(0)

现在看起来您并没有Heap-Delete()跟踪 之外的堆大小length，这可能是反对我的理论的证据。但无论如何，这是我最好的猜测。

于 2013-03-15T16:45:27.363 回答
-1

这里只给出了指向根节点的指针，所以如果你还想删除最后一个节点（对于那些说删除叶节点需要 o(1) 的人）

您必须遍历 log(n) 才能到达叶子，然后只有答案是 b。

于 2017-01-30T12:56:42.797 回答