Вызов MaxHeapify возвращает номера не в исходном массиве.

Я работаю над реализацией max-heap из псевдокода в моей книге и получаю странные результаты после вызова функции buildMaxHeap. Например, целочисленный массив intHeap с элементами {20, 5, 10, 12, 15, 8, 2, 6, 2, 9} приводит к элементам {20, 1066192077, 15, 12, 9, 10, 2, 6 , 2, 5}. Я заметил, что первые 5 элементов почти отсортировано по убыванию, что обнадеживает.

Вот моя реализация до сих пор (с удаленным не относящимся к делу кодом):

#define HEAPSIZE 10
int main()
{
int intHeap[HEAPSIZE] = {20, 5, 10, 12, 15, 8, 2, 6, 2, 9};

std::cout << "Displaying intHeap before buildMaxHeap" << std::endl;
displayHeap(intHeap);
buildMaxHeap(intHeap);
std::cout << "Displaying intHeap after buildMaxHeap" << std::endl;
displayHeap(intHeap);

return 0;
}

// maintains max-heap property for array (sifts down)
template <typename T> void maxHeapify(T* array, int i)
{
// left, right, and largest are positions in the array
int left = i*2, right = i*2+1, largest;

if(left <= HEAPSIZE && array[left] > array[i])
largest = left;
else
largest = i;

if(right <= HEAPSIZE && array[right] > array[largest])
largest = right;

if(largest != i)
{
swap(&array[i], &array[largest]);
maxHeapify(array, largest);
}
}

// builds the max heap
template <typename T> void buildMaxHeap(T* array)
{
for(unsigned int i = HEAPSIZE / 2; i >= 1; i--)
maxHeapify(array, i);
}

У меня действительно много проблем с выяснением того, как десятизначное число оказывается в позиции array [1], поскольку оно даже не принадлежит исходному массиву.

РЕДАКТИРОВАТЬ-> Я думаю, я получил его после этой проблемы индексации массива.

// maintains max-heap property for array (sifts down)
template <typename T> void maxHeapify(T* array, int i)
{
// left, right, and largest are positions in the array
int left = LEFT(i), right = RIGHT(i), largest;

if(left <= (HEAPSIZE - 1) && array[left] > array[i])
largest = left;
else
largest = i;

if(right <= (HEAPSIZE - 1) && array[right] > array[largest])
largest = right;

if(largest != i)
{
swap(&array[i], &array[largest]);
maxHeapify(array, largest);
}
}

// builds the max heap
template <typename T> void buildMaxHeap(T* array)
{
for(int i = (HEAPSIZE-1) / 2; i >= 0; --i)
maxHeapify(array, i);
}

Который, кажется, согласен с примером моей книги. Мне также пришлось изменить переменную i в buildMaxHeap с unsigned int на просто обычное int по какой-то причине (оно показывало значения ниже 0 … Я думал, что unsigned only может быть положительным? Кто-нибудь знает, почему это может произойти?).

В любом случае, спасибо за указание на проблему индексации массива!