Алгоритм max heapify от Cormen с нулевой индексацией

Question

Я пытаюсь реализовать алгоритм 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, то левый ребенок равен 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)

(Вы также можете избежать некоторых проблем, перераспределив один элемент.)