algorithm - MinHeap删除理解

Question

我很难理解我的教授给我的关于堆的问题之一的解决方案。

给出例程 Min-Heap-Delete(A, k) 的伪代码。假设密钥 k 在堆的位置 l 并且 1 ≤ l ≤ n。

我的解决方案是

将 A[k] 与 A[A.size() - 1] 交换

A.size() = A.size() - 1

最小堆(A,k)

但是，我的解决方案与第一部分教授的不同。

将 A[k] 与 A[A.heap_size()] 交换

A.heap_size() = A.heap_size() - 1

最小堆(A,k)

为什么我们要使用 A.size() 而不是 A.size() - 1？由于堆从索引 1 开始，A.size() 不会过度索引代表堆的数组吗？

在这种情况下，A.size() 会给我们 10。但是，A[10] 不存在并且会导致错误。因此，为什么不是 A[10-1] 来获取堆树中的最后一个节点呢？

标签： algorithmdata-structuresheap

Answer 1

因为教授使用从 1 开始的计数，而不是从零开始。注意1 ≤ l ≤ n条件。而且您可能错过了索引是 A. heap_size - 堆大小而不是数组大小，因此最后一个元素将被称为A[9]

对于堆来说这是相当普遍的做法并且很方便，因为子/父索引关系看起来非常简单：

childs = parent * 2 and parent * 2 + 1
parent = child / 2

请注意，图片中的数组实际上是基于 zeo 的，未使用的零条目