HeapSort 的问题

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--)，因为堆是max，不处理第一个元素而对最后一个元素越界。尽管标准中定义了 nth 元素的算术运算，但这并不是 < n 和一些指针工作的意思。

附带说明一下，您可以对 left、right 等函数使用宏 (#defines) 以提高性能并简化阅读。

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

HeapSort 的问题

Issues with HeapSort

c

algorithm

heap

heapsort