堆排序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 [9]交换arr [0]。相反，每次大小减1时，arr [0]应与arr [size]交换。

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); 

}