c - 堆排序无法正常工作

Question

我正在为我的大学用 C 语言编写排序应用程序，并且我对一种算法(堆排序)有疑问。这是我的代码:

void heap_sort(int *array, int size) {
    int temp;

    heap_build(array, size);

    for(int i = size; i>1; i--) {
        temp = array[i];
        array[i] = array[1];
        array[1] = temp;
        size--;
        heap_heapify(array, size, 1);
    }
}

void heap_build(int *array, int size) {
    for(int i = size / 2; i > 0; i--)
        heap_heapify(array, size, i);
}

void heap_heapify(int *array, int size, int i) {
    int largest, temp, 
        l = 2 * i, r = (2 * i) + 1;

    if(l <= size && array[l] > array[i])
        largest = l;
    else 
        largest = i;

    if(r <= size && array[r] > array[largest])
        largest = r;

    if(largest != i) {
        temp = array[largest];
        array[largest] = array[i];
        array[i] = temp;
        heap_heapify(array, size, largest);
    }
}

结果例如:

-22
-33686019 // the range is <-100, 100>
-71
-68
-59
-17
-8
43
59
82

如您所见，数字未正确排序，并且我有一个有线号码(始终在数组[1]中)。

Answer 1

在评论中，您提到您在 1..N 区间内使用数组索引对于大小为 N+1 的数组，但是你传入的大小是 N+1 。如果这是真的，那么 max-heapify() 中就会出现差一错误。 :如果size是 N+1 ，您可以访问的最后一个位置是 N ，不是N+1 ，因此您必须将比较更改为 l < size (对于 r 也类似):

void heap_heapify(int *array, int size, int i) {
    int largest, temp, 
        l = 2 * i, r = (2 * i) + 1;

    if(l < size && array[l] > array[i])
        largest = l;
    else 
        largest = i;

    if(r < size && array[r] > array[largest])
        largest = r;

    if(largest != i) {
        temp = array[largest];
        array[largest] = array[i];
        array[i] = temp;
        heap_heapify(array, size, largest);
    }
}

或者，如果您想让代码尽可能接近 CLRS，您可以使用 <=只要你通过N作为大小而不是 N+1 (因此，您分配一个由 N+1 元素组成的数组，但传递 N 作为大小，因此一切都对齐)。

[旁注:CLRS 使用从 1 开始索引的数组一直困扰着我。在根据那里的伪代码编写实际代码时，这总是会带来麻烦]。

同样的情况发生在 heap_sort() 中，要么你通过它 N作为 N+1 数组的大小元素或初始化 i至size-1 :

void heap_sort(int *array, int size) {
    int temp;

    heap_build(array, size);

    for(int i = size-1; i>1; i--) {
        temp = array[i];
        array[i] = array[1];
        array[1] = temp;
        size--;
        heap_heapify(array, size, 1);
    }
}

这是包含工作代码的完整程序:

#include <stdio.h>

void heap_build(int *array, int size);
void heap_heapify(int *array, int size, int i);

void heap_sort(int *array, int size) {
    int temp;

    heap_build(array, size);

    for(int i = size-1; i>1; i--) {
        temp = array[i];
        array[i] = array[1];
        array[1] = temp;
        size--;
        heap_heapify(array, size, 1);
    }
}

void heap_build(int *array, int size) {
    for(int i = size / 2; i > 0; i--)
        heap_heapify(array, size, i);
}

void heap_heapify(int *array, int size, int i) {
    int largest, temp, 
        l = 2 * i, r = (2 * i) + 1;

    if(l < size && array[l] > array[i])
        largest = l;
    else 
        largest = i;

    if(r < size && array[r] > array[largest])
        largest = r;

    if(largest != i) {
        temp = array[largest];
        array[largest] = array[i];
        array[i] = temp;
        heap_heapify(array, size, largest);
    }
}

int main(void) {
    int arr[] = { 0, -22, 2, -33, 82, 71, 82, 0, -68, -59, -17, -8, 43, 59, -100 };

    heap_sort(arr, sizeof(arr)/sizeof(arr[0]));

    for (int i = 0; i < sizeof(arr)/sizeof(arr[0]); i++) {
        printf("%d\n", arr[i]);
    }

    return 0;
}

打印:

0
-100
-68
-59
-33
-22
-17
-8
0
2
43
59
71
82
82

请注意，第一个元素永远不会排序；因为您使用索引 1..N ，你基本上忽略了元素 0。一个快速的技巧是在数组开始之前传递一个指向一个元素的指针，但这很丑陋，并且 UB (指针算术仅当结果指针引用数组中的元素时才有效)数组，或超过末尾的一个)。

所以我建议重构代码并忘记基于 1 的索引。这可以通过调整计算节点左右子节点的公式并调整循环条件来完成:

#include <stdio.h>

void heap_build(int *array, int size);
void heap_heapify(int *array, int size, int i);

void heap_sort(int *array, int size) {
    int temp;

    heap_build(array, size);

    for(int i = size-1; i > 0; i--) {
        temp = array[i];
        array[i] = array[0];
        array[0] = temp;
        size--;
        heap_heapify(array, size, 0);
    }
}

void heap_build(int *array, int size) {
    for(int i = size/2; i >= 0; i--)
        heap_heapify(array, size, i);
}

void heap_heapify(int *array, int size, int i) {
    int largest, temp,
        l = i*2+1, r = l+1;

    if (l < size && array[l] > array[i])
        largest = l;
    else 
        largest = i;

    if (r < size && array[r] > array[largest])
        largest = r;

    if (largest != i) {
        temp = array[largest];
        array[largest] = array[i];
        array[i] = temp;
        heap_heapify(array, size, largest);
    }
}

int main(void) {
    int arr[] = { 0, -22, 2, -33, 82, 71, 82, 0, -68, -59, -17, -8, 43, 59, -100 };

    heap_sort(arr, sizeof(arr)/sizeof(arr[0]));

    for (int i = 0; i < sizeof(arr)/sizeof(arr[0]); i++) {
        printf("%d\n", arr[i]);
    }

    return 0;
}

与之前版本的区别是:

1. 在 heap_sort ，循环条件变为i > 0 .
2. 在 heap_build() ，循环条件变为i >= 0 .
3. 在 heap_heapify() ，左 child 是 2*i+1而不是2*i ，和r是 2*i+2 .