куча сортировка C - неправильный вывод

Question

Я пытаюсь реализовать сортировку кучи для массива из 10 элементов в порядке возрастания. я после этих шагов -

heap_sort (ARR, size_array):

build_max_heap(arr) 
    for(parent=size_array to 1): 
     swap(arr[1],arr[parent]) 
     size_array = size_array - 1; 
     max_heapify(arr,1,size); 

Но мой вывод полностью перепутались. Я не могу понять, где я ошибаюсь.

Это мой вклад -

20 15 10 1 15 9 2 6 7 9 

Мой выход build_max_heap -

20 15 10 7 15 9 2 6 1 9 

Мой отсортированный массив такой же, как выход build_max_heap -

20 15 10 7 15 9 2 6 1 9 

Что я делаю неправильно ?

Вот мой код:

void max_heapify(int *arr,int i,int size) 
{ 
    //i is the index of parent node. 2i is left child, 2i+1 is right 
    int left = (2*i)+1; 
    int right = (2*i)+2; 
    int max; 
    int temp; 

    //check which node is the max, parent or one of its children. store max idx. 
    if ((left<=size)&&(arr[left]>arr[i])) 
     max = left; 
    else 
     max = i; 
    if ((right<=size)&&(arr[right]>arr[max])) 
     max = right; 

    //swap parent with max. 
    if(max!=i) 
    { 
     temp = arr[max]; 
     arr[max]=arr[i]; 
     arr[i]=temp; 
     max_heapify(arr,max,size); 
    } 

} 

void build_max_heap(int *arr,int size) 
{ 
    for(int i = size/2; i>=0; i--) 
    { 
     max_heapify(arr,i,size); 
    } 
} 

void heap_sort(int *arr, int size) 
{ 
    int temp; 
    build_max_heap(arr,size); 
    int i = size; 
    while(size>0) 
    { 
     //swap 
     temp = arr[i]; 
     arr[i] = arr[0]; 
     arr[0] = temp; 
     //reduce size 
     size = size -1; 
     //heapify 
     max_heapify(arr,0,size); 

    } 
} 

Answer 1

Ваш код обращается к элементу arr[size] несколько раз, что один элемент за пределы допустимого диапазона, 0 <= index < size. В частности:

if ((left<=size)&&(arr[left]>arr[i])) 
    max = left; 
else 
    max = i; 
if ((right<=size)&&(arr[right]>arr[max])) 
    max = right; 

Здесь, вы должны заменить все ... <= size с ... < size.

int temp; 
build_max_heap(arr,size); 
int i = size; 
while(size>0) 
{ 
    //swap 
    temp = arr[i]; 
    arr[i] = arr[0]; 
    arr[0] = temp; 
    //reduce size 
    size = size -1; 
    //heapify 
    max_heapify(arr,0,size); 

} 

Здесь используются две переменные, i и size, но обновлять только size. Индекс i всегда будет за пределами допустимого диапазона, потому что i < size никогда не будет истинным. Вы должны использовать и изменять только одну переменную через цикл.

Вы можете полностью опустить i, но обратите внимание, как вы всегда будете получать доступ к элементу за одно место за пределами массива. Поэтому перед тем, как вы меняете элементы, вы должны уменьшить size.

(Вы можете заключить контракт while (size > 0) { size = size - 1; ...} к while (size--) ... Это полезный прием для перемещения вперед: задом итераций decreease индекса перед телом цикла, вперед итерации увеличения индекса после тела цикла.).

Собираем все вместе:

void max_heapify(int *arr, int i, int size) 
{ 
    //i is the index of parent node. 2i is left child, 2i+1 is right 
    int left = 2*i + 1; 
    int right = 2*i + 2; 
    int max; 

    if (left < size && arr[left] > arr[i]) 
     max = left; 
    else 
     max = i; 

    if (right < size && arr[right] > arr[max]) 
     max = right; 

    if (max != i) { 
     int temp = arr[max]; 
     arr[max]=arr[i]; 
     arr[i]=temp; 

     max_heapify(arr,max,size); 
    } 

} 

void build_max_heap(int *arr,int size) 
{ 
    int i = size/2; 

    while (i--) { 
     max_heapify(arr, i, size); 
    } 
} 

void heap_sort(int *arr, int size) 
{ 
    build_max_heap(arr, size); 

    while (size--) { 
     int temp = arr[size]; 
     arr[size] = arr[0]; 
     arr[0] = temp; 

     max_heapify(arr, 0, size); 
    } 
} 

Answer 2

в вашем heap_sort i должен быть установлен в размере в пределах цикла. С тем, как у вас есть, вы меняете arr [0] с arr [9] каждый раз. Вместо этого arr [0] должен меняться с помощью arr [size] каждый раз, когда размер уменьшается на 1.

int i = size; //Here is your main problem 
while(size>0) 
{ 
    //swap 
    temp = arr[i]; 
    arr[i] = arr[0]; 
    arr[0] = temp; 
    //reduce size 
    size = size -1; 
    //heapify 
    max_heapify(arr,0,size); 

}