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

Question

Я работаю над реализацией 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);
}

У меня действительно много проблем с выяснением того, как десятизначное число заканчивается в массиве [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 может быть положительным? Кто-нибудь знает, почему это может произойти?).

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

Answer 1

В C++ массивы основаны на нуле, т. Е. Массив n элементы использует индексы 0, 1,..., n-1, Ваш код предполагает, что он один.

Answer 2

1) Что говорит вам ваш отладчик?

2) Что в вашей функции, если слева == HEAPSIZE или справа == HEAPSIZE?

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

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

Затем вы продолжаете и получаете доступ к массиву [Large], который находится за пределами.