C语言中如何用数组指针实现最小堆排序？堆创建/堆化函数排障

我懂你现在的困境——想用带数组指针的结构体实现最小堆来做堆排序，但卡在createHeap或者heapify的逻辑错误上了。按照你的要求，我只调整这两个函数，不碰程序其他部分。

先把你提供的代码片段完整呈现（补全缺失的函数声明部分）：

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

// 存储数组指针与堆大小的最小堆结构体
struct MinHeap{
    int size;
    int* array;
};

// 函数声明
void createHeap(struct MinHeap* heap, int arr[], int n);
void heapify(struct MinHeap* heap, int i);
// 假设程序其余部分还有堆排序相关函数（比如extractMin等）

修正后的heapify函数 #

最小堆的heapify核心逻辑是：确保当前节点的值小于等于左右子节点，若不满足则与最小的子节点交换，再递归处理被交换的子节点。

void heapify(struct MinHeap* heap, int i) {
    int smallest = i; // 初始化最小元素为当前节点
    int left = 2 * i + 1; // 左子节点索引
    int right = 2 * i + 2; // 右子节点索引
    int heapSize = heap->size;
    int* heapArr = heap->array;

    // 若左子节点存在且比当前最小节点小，更新最小节点索引
    if (left < heapSize && heapArr[left] < heapArr[smallest]) {
        smallest = left;
    }

    // 若右子节点存在且比当前最小节点小，更新最小节点索引
    if (right < heapSize && heapArr[right] < heapArr[smallest]) {
        smallest = right;
    }

    // 若最小节点不是当前节点，交换后递归调整子树
    if (smallest != i) {
        int temp = heapArr[i];
        heapArr[i] = heapArr[smallest];
        heapArr[smallest] = temp;
        heapify(heap, smallest);
    }
}

修正后的createHeap函数 #

创建最小堆需要先完成结构体的初始化（内存分配、数组复制、大小设置），再从最后一个非叶子节点开始倒序执行heapify，这样能高效构建出符合要求的最小堆。

void createHeap(struct MinHeap* heap, int arr[], int n) {
    heap->size = n;
    // 为堆的数组指针分配内存
    heap->array = (int*)malloc(n * sizeof(int));
    if (heap->array == NULL) {
        fprintf(stderr, "内存分配失败！\n");
        exit(EXIT_FAILURE);
    }
    // 将输入数组的内容复制到堆的数组中
    for (int i = 0; i < n; i++) {
        heap->array[i] = arr[i];
    }

    // 从最后一个非叶子节点开始，倒序执行heapify构建堆
    for (int i = (n / 2) - 1; i >= 0; i--) {
        heapify(heap, i);
    }
}

关键说明 #

• heapify函数严格遵循最小堆的定义，始终保证父节点是当前子树的最小值；
• createHeap函数选择从最后一个非叶子节点开始处理，避免了对叶子节点的无效操作，构建堆的时间复杂度为O(n)，是最优的构建方式。

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