数据结构堆排序找错，求回复

Question

#include <stdio.h>

void temp(int &x,int &y)
{
    int t;
    t=x;
    x=y;
    y=t;
}

void Heapify(int a[],int start,int end)
{
    int dad,son;


    dad=(end-1)/2;
    son=2*dad+1;
    if(son+1<=end)
    {
        if(a[son]<a[son+1])
            son=son+1;
    }

    while(dad>=0)
    {
        while(a[son]>a[dad])
        {
            temp(a[son],a[dad]);

            if(son<=(end+1)/2)
            {
                dad=son;
                son=2*dad+1;
                if(son+1<=end)
                {
                    if(a[son]<a[son+1])
                        son=son+1;
                }
            }
        }


        dad--;
        son=2*dad+1;
        if(son+1<=end)
        {
            if(a[son]<a[son+1])
                son=son+1;
        }

    }



}

void HeapSort(int a[],int start,int end)
{
    Heapify(a,start,end);

    int i;
    for(i=end;i>0;i--)
    {
        temp(a[0],a[i]);
        Heapify(a,start,i);
    }
}




int main()
{
    int a[10]={3,87,2,93,78,56,61,38,12,40};

    HeapSort(a,0,9);
}

Answer 1

晚上好🌙🌙🌙
本答案参考ChatGPT-3.5

在你的代码中，HeapSort 函数存在一个错误，它在每次交换最大值到末尾后没有正确地重新调用 Heapify。这会导致堆的性质破坏，影响排序结果。以下是修复后的代码：

#include <stdio.h>

void temp(int &x, int &y) {
    int t;
    t = x;
    x = y;
    y = t;
}

void Heapify(int a[], int start, int end) {
    int dad, son;

    dad = (end - 1) / 2;
    son = 2 * dad + 1;

    if (son + 1 <= end) {
        if (a[son] < a[son + 1])
            son = son + 1;
    }

    while (dad >= 0) {
        while (a[son] > a[dad]) {
            temp(a[son], a[dad]);

            if (son <= (end + 1) / 2) {
                dad = son;
                son = 2 * dad + 1;
                if (son + 1 <= end) {
                    if (a[son] < a[son + 1])
                        son = son + 1;
                }
            }
        }

        Heapify(a, start, dad); // 这里添加了对 dad 的递归调用

        dad--;
        son = 2 * dad + 1;
        if (son + 1 <= end) {
            if (a[son] < a[son + 1])
                son = son + 1;
        }
    }
}

void HeapSort(int a[], int start, int end) {
    Heapify(a, start, end);

    int i;
    for (i = end; i > 0; i--) {
        temp(a[0], a[i]);
        Heapify(a, start, i - 1); // 修改为 i - 1，因为每次下移一个元素
    }
}

int main() {
    int a[10] = {3, 87, 2, 93, 78, 56, 61, 38, 12, 40};

    HeapSort(a, 0, 9);
    return 0;
}

现在，HeapSort 函数已经修复，它会在每次交换后正确地重新构建子树，以保持堆的特性。这样，排序结果应该是正确的。