Проблемы с HeapSort

Question

моей задачей является написать код в heapsort в соответствии с псевдокодом. Он должен распаковать входной массив (4 3 2 5 6 7 8 9 12 1), а затем распечатать его с помощью метода printHeap. Я знаю, что printHeap работает, потому что я уже использовал его с помощью метода buildHeap (для создания массивных кучных двоичных деревьев, но вы все уже знаете это :)), и там он работает безупречно, поэтому моя проблема кроется в heapSort ,

Он правильно сортирует и печатает его так, как это предполагается (родительский - ребенок 1, родительский - 2 и т. Д.), Только проблема заключается в том, что самое большое и последнее значение, которое равно 12, внезапно превращается в 24 и я не знаю, почему.

Код следующее:

void heapSort(int a[], int n){ 
int x = n+1; 
int i; 
int temp; 
buildMaxHeap(a, n); 
for (i = n; i >= 1; i--){ 
    temp = a[i]; 
    a[i] = a [0]; 
    a [0] = temp; 
    x--; 
    heapify(a, 0, x); 
} 

void printHeap(int a[], int n){ 

int i; 
printf("graph g { \n"); 
for (i = 0; i < n/2; i++){ 
    printf("%d -- %d\n", a[i], a[left(i)]); 
    if (right(i) < n){ 
     printf("%d -- %d\n", a[i], a[right(i)]); 
    } 
} 
printf("}\n"); 

Вывод следующий:

1 2 3 4 5 6 7 8 9 24 
graph g { 
1 -- 2 
1 -- 3 
2 -- 4 
2 -- 5 
3 -- 6 
3 -- 7 
4 -- 8 
4 -- 9 
5 -- 24 
} 

просто так что вы точно знаете, что я сделал, я присоединит время .c файл здесь: https://onedrive.live.com/redir?resid=8BC629F201D2BC63!26268&authkey=!AFqVlm9AptiZ_xM&ithint=file%2cc

Действительно благодарен вам за помощь!

Приветствия Арик

Answer 1

Ну, вы наблюдаете неопределенное поведение. (Я лично на онлайн IDE получил 0 вместо 12 (24).)

Try:

void heapSort(int a[], int n) 
{ 
    int x = n; /* changed from n+1 */ 
    int i; 
    int temp; 

    buildMaxHeap(a, n); 
    for (i = n-1; i >= 0; i--){ /*<-- changed*/ 
     temp = a[i]; 
     a[i] = a[0]; 
     a[0] = temp; 
     x--; 
     heapify(a, 0, x); 
    } 
} 

Ваши массивы почти на всех языках общего назначения сегодня начинаются с индекса 0 [Для основательной информации см wiki.] Вы ошибочно зацикливаете свой массив for (i = n; i >= 1; i--), а так как куча макс, не обрабатывайте первый элемент и не выходите за пределы с последним. Хотя арифметика с элементом nth определена в стандарте, это не значит, что это скорее < n, а некоторый указатель работает.

На боковой ноте вы можете использовать макросы (#define s) для функций left, right и т. Д., Чтобы улучшить производительность и облегчить чтение.

Я надеюсь, что это экономит день и AlgoDat Упражнение.