基于零索引的Cormen最大堆算法

Question

我正在尝试实现算法书中给出的最大堆算法here书中的算法是

 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)

我的问题是，我的数组是从Zero.Where开始的，就像在书中一样，他们假设如果父代的索引是i，那么左子元素是2i，右子元素是2i+1，但这是当它们的索引从1开始时，在我的例子中，它是0，那么我应该如何计算左子元素和右子元素的索引？

Answer 1

左边的孩子在2i+1，右边的孩子在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)

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