堆排序 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--) ...。这是向后迭代的一个有用的习惯用法：向后迭代减少循环体之前的索引；向前迭代增加循环体之后的索引。）

综合起来：

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] 交换。相反，每次大小减 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);

}

堆排序 C - 不正确的输出

heap sort C - improper output

c

arrays

sorting

heapsort