algorithm - MinHeap删除理解

Question

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

Give pseudocode for the routine Min-Heap-Delete(A, k). Assume that key k is at location l of the heap and that 1 ≤ l ≤ n.

我的解决办法是

Exchange A[k] with A[A.size() - 1]

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

Min-heapify(A,k)

但是，我的解法和第一部分教授的解法有区别。

Exchange A[k] with 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]获取堆树的最后一个节点呢？

Answer 1

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

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

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

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