堆排序不能正常工作

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() 中有一个 off-by-one 错误：如果 size 是 N+1，你可以访问的最后一个位置是 N，而不是 [=16] =]，因此您必须将比较更改为 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+1 元素数组的大小传递 N，要么将 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;
}

这会打印：

请注意，第一个元素永远不会排序；因为你使用索引 1..N，所以你基本上忽略了元素 0。一个快速的 hack 是在数组开始之前传递一个指向一个元素的指针，但这很丑陋，而且 UB（指针算法仅有效如果结果指针引用数组中的一个元素，或者引用数组末尾的一个元素）。

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

#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;
}

与上一版本的区别是：

在heap_sort中，循环条件变为i > 0。
在heap_build()中，循环条件变为i >= 0。
在heap_heapify()中，左边的child是2*i+1而不是2*i，r是2*i+2。

堆排序不能正常工作

Heap Sort doesn't work properly

c

sorting

heapsort