C语言堆排序实现异常：数组未排序问题求助

我仔细看了你的代码，发现几个关键错误导致堆排序失败，下面逐一分析并给出修正方案：

1. is_higher 宏的逻辑完全错误 #

你写的is_higher宏返回的是两个值中较大的那个，而不是判断第一个值是否大于第二个值。这会导致siftDown函数的逻辑完全颠倒：

#define is_higher(a, b) (((a) > (b))? (a) : (b))

比如当父节点值3小于子节点值5时，is_higher(3,5)返回5（非零），此时if(is_higher(...)) return;会直接退出函数，跳过本该执行的交换操作，导致堆的下沉逻辑完全失效。

修正：让宏返回布尔值（1表示a大于b，0表示否则）：

#define is_higher(a, b) ((a) > (b))

2. 堆构建的起始索引错误 #

在array2heap函数中，你从closest_lower_p2(h->size) -1开始执行siftDown，但正确的堆构建应该从最后一个非叶子节点开始，也就是(h->size - 2) / 2（等价于h->size//2 -1）。

你的closest_lower_p2方法会导致跳过前面的非叶子节点，比如当数组大小为10时，最后一个非叶子节点是索引4，但你的代码从索引7开始，导致前5个节点没有执行下沉，堆结构无法正确建立。

修正：替换堆构建的循环起始条件：

// 原代码
for(i = closest_lower_p2(h->size) - 1; i >=0; i--)
// 修正后
for(i = (h->size - 2) / 2; i >= 0; i--)

同时可以删掉closest_lower_p2函数，因为不再需要它。

3. heap_print函数的越界访问 #

heap_print中的循环条件u <= h->size会访问h->array[h->size]，而堆的有效索引范围是0到h->size-1，这会导致数组越界，可能破坏内存数据。

修正：把循环条件改为u < h->size：

for(u = 0; u < h->size; u++)

4. siftDown循环条件的小问题 #

原代码中left_child_index(i) <= h->size的判断会包含无效索引（比如h->size对应的位置不属于堆元素），修正为left_child_index(i) < h->size，确保只处理存在的子节点。

修正后的完整代码 #

下面是修复后的核心代码部分，其他辅助函数（如array_print、测试函数）做了适配调整：

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#define DEBUG_MODE 1
// 修正is_higher宏为布尔判断
#define is_higher(a, b) ((a) > (b))
#define left_child_index(i) (((i + 1) << 1)-1)
#define right_child_index(i) (((i + 1) << 1))
#define HEAP_SORT_TEST_ARRAY_SIZE 10
#define HEAP_SORT_TEST_TEST_TIMES 8
#define is_odd(u) (u - ((u >> 1) << 1))

typedef int b_heap_entry;
typedef struct heap {
    b_heap_entry* array;
    int capacity;
    int size;
} b_heap;

void array_print(int* array, unsigned size) {
    unsigned u;
    printf("[");
    for(u = 0; u < size; u++)
        printf("%d, ", array[u]);
    printf("\b\b]\n");
}

#if DEBUG_MODE
int is_power2(unsigned u) {
    if(u == 0) return 0;
    return (u & (u - 1)) == 0;
}

void heap_print(b_heap* h) {
    printf("BINARY HEAP:\n(size %d)\n", h->size);
    unsigned u;
    for(u = 0; u < h->size; u++) {
        if(is_power2(u+1))
            printf("\n");
        printf("<%d> ", h->array[u]);
    }
    printf("\n");
}
#endif

inline void siftDown(b_heap* h, int i) {
    int child_index;
    b_heap_entry tmp;
    // 修正循环条件：只处理存在的左子节点
    while(left_child_index(i) < h->size) {
        // 判断右子节点是否存在且更大
        if(right_child_index(i) < h->size && is_higher(h->array[right_child_index(i)], h->array[left_child_index(i)])) {
            child_index = right_child_index(i);
        } else {
            child_index = left_child_index(i);
        }
        // 当前节点大于等于子节点时停止下沉
        if(is_higher(h->array[i], h->array[child_index]))
            return;
        // 交换节点
        tmp = h->array[i];
        h->array[i] = h->array[child_index];
        h->array[child_index] = tmp;
        i = child_index;
    }
}

b_heap_entry heap_poll(b_heap* h) {
    b_heap_entry root = h->array[0];
    // 交换根节点与最后一个有效元素
    h->array[0] = h->array[h->size - 1];
    h->size--;
    siftDown(h, 0);
    return root;
}

b_heap* array2heap(int * array, int size) {
#if DEBUG_MODE
    printf("Making the array\n");
    array_print(array, size);
    printf("into a binary heap...\n");
#endif
    b_heap* h = malloc(sizeof(b_heap));
    h->size = size;
    h->capacity = size;
    h->array = array;
    // 从最后一个非叶子节点开始构建堆
    int i;
    for(i = (size - 2) / 2; i >= 0; i--)
        siftDown(h, i);
#if DEBUG_MODE
    heap_print(h);
    printf("done...\n");
#endif
    return h;
}

void heap_sort(int * array, int size) {
    b_heap* h = array2heap(array, size);
    while(size > 0) {
        array[--size] = heap_poll(h);
    }
    free(h);
}

inline void array_fill_with_rand(int* array, unsigned size) {
    unsigned i;
    for(i = 0; i < size; i++)
        array[i] = rand() % 100; // 限制随机数范围，方便测试观察
}

int heap_sort_test() {
    unsigned u, w;
    int array[HEAP_SORT_TEST_ARRAY_SIZE];
    srand(42); // 设置随机种子，确保测试可复现
    for(u = 0; u < HEAP_SORT_TEST_TEST_TIMES; u++) {
        array_fill_with_rand(array, HEAP_SORT_TEST_ARRAY_SIZE);
#if DEBUG_MODE
        printf("Array n%d before sorting:\n", u);
        array_print(array, HEAP_SORT_TEST_ARRAY_SIZE);
#endif
        heap_sort(array, HEAP_SORT_TEST_ARRAY_SIZE);
#if DEBUG_MODE
        printf("Array n%d after sorting:\n", u);
        array_print(array, HEAP_SORT_TEST_ARRAY_SIZE);
#endif
        for(w = 0; w < HEAP_SORT_TEST_ARRAY_SIZE - 1; w++) {
            if(array[w] > array[w+1]) {
                printf("Test n.%d failed...\n(%d is higher than %d)\nAbort...", u, array[w], array[w+1]);
                return 0;
            }
        }
        printf("Test n.%d pass\n", u);
    }
    return 1;
}

int main() {
    heap_sort_test();
    return 0;
}

测试验证 #

修正后的代码会正确执行堆排序：

• 构建堆时从正确的节点开始下沉，确保堆结构符合最大堆要求
• siftDown逻辑正常，能正确交换节点并维护堆属性
• 排序后的数组会按升序排列（因为每次把最大值放到数组末尾）

运行测试函数后，所有测试用例都会通过，数组会被正确排序。

内容的提问来源于stack exchange，提问作者user2704673