关于HeapSort的问题

Question

我的任务是根据伪代码将代码写入堆排序。它应该对输入数组( input，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文件：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开始[有关详细信息，请参阅维基]。您错误地循环了数组for (i = n; i >= 1; i--)，由于堆是最大的，所以不要处理第一个元素并与最后一个元素超出界限。尽管在标准中定义了带有nth元素的算术，但它并不意味着< n和某些指针工作。

另外，您可以使用宏(#defines)来实现left、right等函数，以提高性能并简化读取。

我希望这能节省时间和AlgoDat练习。