来自Cormen的max heapify算法,具有零索引

Question

我想实现的算法给出书最大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)

我的问题是我的数组从Zero开始.在书中他们认为如果父母的索引是i,那么左子是2i而右子是2i + 1但是当他们的索引从1开始时.在我的情况下它是零所以我应该如何计算左右孩子的指数？

Answer 1

左边的孩子是2i + 1,右边的孩子是2(i + 1)= 2i + 2.

您可以通过调用基于单的索引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)

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