c - 来自 Cormen 的 max heapify 算法，具有零索引

Question

我正在尝试实现算法书 here 中给出的 max heapify 算法书中的算法是

 MAX-HEAPIFY(A,i)
1   l<-LEFT(i)
2   r<-RIGHT(i)
3  if l<=heap-size[A] and A[l]>A[i]
4    then largest<--l
5    else largest<--i
6 if r<=heap-size[A] and A[r]>A[largest]
7    then largest <->r
8 if largest!=i
9    then exchange A[i]<->A[largest]
10        MAX-HEAPIFY(A,largest)

我的问题是我的数组是从零开始的。在书中他们假设如果父索引是 i 那么左 child 是 2i 右 child 是 2i+1 但那是他们的索引从 1 开始的时候。在我的如果它是零那么我应该如何计算左右 child 的索引？

Answer 1

左 child 在 2i+1，右 child 在 2(i+1) = 2i+2。

您可以通过调用基于 1 的索引 j、定义 i = j - 1 并观察它来证明这是正确的

j = i + 1
left + 1  = 2j = 2(i+1) = 2i+2
right + 1 = 2j+1 = 2(i+1) + 1

所以

left = 2i+1
right = 2(i+1)

(您也可以通过过度分配单个元素来省去一些麻烦。)