当前位置：首页 > news >正文

堆的C语言实现

news 2025/5/23 10:59:41

一、堆的本质与核心特性

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

结构特性：

完全二叉树：所有层除最后一层外都是满的，且最后一层的节点尽量靠左排列。
数组存储：堆的物理存储使用数组，逻辑上映射为树形结构。父子节点下标关系：

父节点：parent = (child-1)/2
左子节点:left_child = parent *2 +1;
右子节点: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）

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

步骤：

将元素插入数组末尾。
向上调整：若新元素值大于父节点（大顶堆），则交换父子节点，直到满足堆性质。

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

时间复杂度：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）

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

步骤：

将堆顶元素与末尾元素交换。
删除末尾元素（原堆顶）。
向下调整：从堆顶开始，若父节点小于子节点，则交换并继续调整。

时间复杂度：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);}
}