堆的C语言实现

一、堆的本质与核心特性

堆（Heap）是一种基于完全二叉树的抽象数据结构，具有以下核心特性：

结构特性：

• 完全二叉树：所有层除最后一层外都是满的，且最后一层的节点尽量靠左排列。

• 数组存储：堆的物理存储使用数组，逻辑上映射为树形结构。父子节点下标关系：

1. 父节点：parent = (child-1)/2

2. 左子节点:left_child = parent *2 +1;

3. 右子节点:right_child = parent *2 +2

有序性：

• 大顶堆：父节点的值 ≥ 子节点的值。

• 小顶堆：父节点的值 ≤ 子节点的值。

二、堆与顺序表的联系

 堆的实现依赖于顺序表（动态数组），但两者在功能上有本质区别：

为什么用顺序表实现堆？

• 完全二叉树的特性保证了数组存储的紧凑性，无需指针即可通过下标计算父子节点关系。

• 父子节点的下标关系可通过公式直接计算，访问时间复杂度为 O(1)。

 三、堆的核心操作与代码实现

 1. 堆的初始化与销毁

• 初始化：设置数组指针为NULL，容量和大小初始化为0。

• 销毁：释放动态数组内存，防止内存泄漏。

typedef struct Heap {
    HPDataType* arr;  // 动态数组
    int size;         // 当前元素个数
    int capacity;     // 数组容量
} HP;

// 初始化堆
void HPInit(HP* php) {
    assert(php);
    php->arr = NULL;
    php->size = php->capacity = 0;
}

// 销毁堆
void HPDestroy(HP* php) {
    assert(php);
    free(php->arr);
    php->arr = NULL;
    php->size = php->capacity = 0;
}

 2. 插入元素（Push）与向上调整（AdjustUp）

目标：插入新元素后，维护堆的有序性。

步骤：

1. 将元素插入数组末尾。

2. 向上调整：若新元素值大于父节点（大顶堆），则交换父子节点，直到满足堆性质。

自下而上建堆：从最后一个非叶子节点开始，逐个向上调整。

时间复杂度：O(log N)。每次插入最多调整树的高度（log N层）。

适用场景：通过已有数组构建堆。

void AdjustUp(HPDataType* a, int child) {
    int parent = (child - 1) / 2;
    while (child > 0) {  // 循环至根节点
        if (a[child] > a[parent]) {  // 大顶堆：子节点 > 父节点则交换
            Swap(&a[child], &a[parent]);
            child = parent;          // 上移至父节点
            parent = (child - 1) / 2;
        } else {
            break;  // 堆性质已满足
        }
    }
}

void HPPush(HP* php, HPDataType x) {
    assert(php);
    // 动态扩容（容量不足时翻倍扩容）
    if (php->size == php->capacity) {
        size_t newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
        HPDataType* tmp = realloc(php->arr, sizeof(HPDataType) * newCapacity);
        if (tmp == NULL) {
            perror("realloc fail");
            return;
        }
        php->arr = tmp;
        php->capacity = newCapacity;
    }
    // 插入元素并调整
    php->arr[php->size] = x;
    php->size++;
    AdjustUp(php->arr, php->size - 1);  // 从新元素位置向上调整
}

3. 删除堆顶元素（Pop）与向下调整（AdjustDown）

• 目标：删除堆顶元素后，维护堆的有序性。

 步骤：

1. 将堆顶元素与末尾元素交换。

2. 删除末尾元素（原堆顶）。

3. 向下调整：从堆顶开始，若父节点小于子节点，则交换并继续调整。

时间复杂度：O(log N)。每次删除最多调整树的高度。

void AdjustDown(HPDataType* a, int n, int parent) {
    int child = parent * 2 + 1;  // 左子节点
    while (child < n) {
        // 选择较大的子节点（大顶堆）
        if (child + 1 < n && a[child + 1] > a[child]) {
            child++;
        }
        // 若父节点 < 子节点，则交换并继续调整
        if (a[child] > a[parent]) {
            Swap(&a[child], &a[parent]);
            parent = child;
            child = parent * 2 + 1;
        } else {
            break;  // 堆性质已满足
        }
    }
}

void HPPop(HP* php) {
    assert(php && php->size > 0);
    Swap(&php->arr[0], &php->arr[php->size - 1]);  // 交换堆顶与末尾元素
    php->size--;
    AdjustDown(php->arr, php->size, 0);  // 从堆顶向下调整
}

4. 堆化（Heapify）与建堆

• 目标：将任意数组转换为堆。

• 方法：从最后一个非叶子节点开始，自底向上执行向下调整。

void HPInitArray(HP* php, HPDataType* a, int n) {
    assert(php);
    php->arr = (HPDataType*)malloc(n * sizeof(HPDataType));
    memcpy(php->arr, a, n * sizeof(HPDataType));
    php->size = php->capacity = n;

    // 从最后一个非叶子节点开始调整
    for (int parent = (n - 2) / 2; parent >= 0; parent--) {
        AdjustDown(php->arr, n, parent);
    }
}

四、总结

堆的核心在于通过向上调整（AdjustUp）和向下调整（AdjustDown）维护堆性质。其实现依赖动态数组，结合完全二叉树的特性，使得插入、删除和获取极值的操作高效（O(log N)）。可扩展以下内容：

1. 小顶堆：修改比较逻辑（将 > 改为 <）。

2. 堆排序：通过反复交换堆顶与末尾元素实现排序。

3. 优先队列：结合堆的性质实现任务调度。

堆的核心价值：

• 以 O(1) 时间复杂度获取极值，插入和删除操作仅需 O(log N)。

• 空间利用率高，无需额外指针存储树结构。