c - 堆排序的问题

Question

我的任务是根据伪代码将代码写入堆排序。它应该对输入数组( 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
}

为了让您知道我到底做了什么，我将在此处附加 while .c 文件: https://onedrive.live.com/redir?resid=8BC629F201D2BC63!26268&authkey=!AFqVlm9AptiZ_xM&ithint=file%2cc

非常感谢您的帮助!

干杯 阿里克

Answer 1

好吧，您观察到了未定义的行为。 (我个人在在线 IDE 上得到 0 而不是 12 ( 24 )。)

尝试:

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 使用宏( left s) , right等功能来提高性能并简化阅读。

我希望这能挽救局面并拯救 AlgoDat 练习。