什么是堆（Heap）？
堆是一种特殊的树形数据结构，它满足以下两个主要属性：
结构性（完全二叉树）：
堆总是一个完全二叉树 (Complete Binary Tree)。这意味着，除了最后一层，所有的层都是完全填充的，并且最后一层的所有节点都尽可能地向左填充。
这个特性使得堆非常适合用数组来表示，因为节点之间的父子关系可以通过索引轻松计算。
堆序性（Heap Property）：
最大堆（Max-Heap）： 在一个最大堆中，每个父节点的值都大于或等于其子节点的值。这意味着，根节点是整个堆中的最大元素。
最小堆（Min-Heap）： 在一个最小堆中，每个父节点的值都小于或等于其子节点的值。这意味着，根节点是整个堆中的最小元素。
总结： 堆是一个用数组实现的完全二叉树，并且满足特定的堆序性（父节点大于等于子节点或小于等于子节点）。
堆的ADT（抽象数据类型）操作
一个典型的堆通常支持以下操作：
createHeap(capacity): 创建一个指定容量的空堆。isFull(heap): 检查堆是否已满。isEmpty(heap): 检查堆是否为空。insert(heap, value): 将新元素插入堆中，并保持堆的性质。deleteMax(heap)/deleteMin(heap): 删除堆中最大/最小元素（通常是根节点），并保持堆的性质。peekMax(heap)/peekMin(heap): 查看堆中最大/最小元素（根节点），但不删除。heapifyUp(heap, index): 向上调整堆，当子节点的值发生变化（通常是插入操作后）。heapifyDown(heap, index): 向下调整堆，当父节点的值发生变化（通常是删除操作或建堆操作后）。buildHeap(array, size): 将一个无序数组转换为一个堆。
堆的C语言实现原理（基于数组）
由于堆是完全二叉树，它最常用的实现方式是使用数组。这种实现方式的优点在于：
空间效率高： 无需存储指针。
计算效率高： 父子节点的关系可以通过简单的算术运算得出。
对于一个基于0索引的数组 arr：
根节点：
arr[0]节点
i的左子节点：arr[2 * i + 1]节点
i的右子节点：arr[2 * i + 2]节点
i的父节点：arr[(i - 1) / 2](注意整数除法)
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h> // For bool type
// -----------------------------------------------------------
// 1. 定义堆结构体
// -----------------------------------------------------------
typedef struct MaxHeap {
int* arr; // 存储堆元素的数组
int capacity; // 堆的最大容量
int size; // 堆当前元素的数量
} MaxHeap;
// -----------------------------------------------------------
// 2. 辅助函数
// -----------------------------------------------------------
// 交换两个整数的值
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
// -----------------------------------------------------------
// 3. 核心堆操作函数
// -----------------------------------------------------------
// 创建一个空的MaxHeap
MaxHeap* createMaxHeap(int capacity) {
MaxHeap* newHeap = (MaxHeap*)malloc(sizeof(MaxHeap));
if (newHeap == NULL) {
perror("Failed to allocate memory for MaxHeap structure");
exit(EXIT_FAILURE);
}
newHeap->arr = (int*)malloc(sizeof(int) * capacity);
if (newHeap->arr == NULL) {
perror("Failed to allocate memory for MaxHeap array");
free(newHeap); // Clean up partially allocated memory
exit(EXIT_FAILURE);
}
newHeap->capacity = capacity;
newHeap->size = 0;
printf("MaxHeap created with capacity: %d\n", capacity);
return newHeap;
}
// 释放堆占用的内存
void destroyMaxHeap(MaxHeap* heap) {
if (heap != NULL) {
free(heap->arr);
heap->arr = NULL;
free(heap);
printf("MaxHeap destroyed.\n");
}
}
// 检查堆是否为空
bool isEmpty(MaxHeap* heap) {
return heap->size == 0;
}
// 检查堆是否已满
bool isFull(MaxHeap* heap) {
return heap->size == heap->capacity;
}
// 获取父节点的索引
int getParentIndex(int i) {
return (i - 1) / 2;
}
// 获取左子节点的索引
int getLeftChildIndex(int i) {
return 2 * i + 1;
}
// 获取右子节点的索引
int ietRightChildIndex(int i) {
return 2 * i + 2;
}
// 判断给定索引是否具有左子节点
bool hasLeftChild(MaxHeap* heap, int i) {
return getLeftChildIndex(i) < heap->size;
}
// 判断给定索引是否具有右子节点
bool hasRightChild(MaxHeap* heap, int i) {
return ietRightChildIndex(i) < heap->size;
}
/**
* @brief 向上调整堆 (Heapify Up)
* 当子节点的值大于父节点时，将其与父节点交换，直到满足堆性质或到达根节点。
* 通常在插入新元素后调用。
*
* @param heap 指向MaxHeap的指针
* @param index 待调整元素的当前索引
*/
void heapifyUp(MaxHeap* heap, int index) {
// 当当前节点不是根节点，且当前节点的值大于其父节点的值时
while (index > 0 && heap->arr[getParentIndex(index)] < heap->arr[index]) {
swap(&heap->arr[index], &heap->arr[getParentIndex(index)]);
index = getParentIndex(index); // 移动到父节点的位置，继续向上检查
}
}
/**
* @brief 向下调整堆 (Heapify Down)
* 当父节点的值小于其子节点时，将其与最大的子节点交换，直到满足堆性质或到达叶子节点。
* 通常在删除根元素或建堆时调用。
*
* @param heap 指向MaxHeap的指针
* @param index 待调整元素的当前索引
*/
void heapifyDown(MaxHeap* heap, int index) {
int maxIndex = index;
int leftChild = getLeftChildIndex(index);
int rightChild = ietRightChildIndex(index);
// 检查左子节点是否存在且大于当前最大值
if (hasLeftChild(heap, index) && heap->arr[leftChild] > heap->arr[maxIndex]) {
maxIndex = leftChild;
}
// 检查右子节点是否存在且大于当前最大值
if (hasRightChild(heap, index) && heap->arr[rightChild] > heap->arr[maxIndex]) {
maxIndex = rightChild;
}
// 如果maxIndex不是当前index，说明子节点比父节点大，需要交换
if (maxIndex != index) {
swap(&heap->arr[index], &heap->arr[maxIndex]);
heapifyDown(heap, maxIndex); // 递归向下调整
}
}
/**
* @brief 插入一个元素到最大堆
* 将新元素放到数组末尾，然后向上调整以维护堆性质。
*
* @param heap 指向MaxHeap的指针
* @param value 要插入的值
* @return true 插入成功
* @return false 堆已满，插入失败
*/
bool insert(MaxHeap* heap, int value) {
if (isFull(heap)) {
printf("Error: Heap is full. Cannot insert %d.\n", value);
return false;
}
heap->arr[heap->size] = value; // 将新元素放到数组末尾
heap->size++; // 堆大小加1
heapifyUp(heap, heap->size - 1); // 从新元素位置向上调整
printf("Inserted: %d\n", value);
return true;
}
/**
* @brief 从最大堆中删除最大元素（根元素）
* 将根元素与最后一个元素交换，然后删除最后一个元素，最后向下调整新的根元素。
*
* @param heap 指向MaxHeap的指针
* @param deletedValue 用于存储被删除的值的指针
* @return true 删除成功
* @return false 堆为空，删除失败
*/
bool deleteMax(MaxHeap* heap, int* deletedValue) {
if (isEmpty(heap)) {
printf("Error: Heap is empty. Cannot delete.\n");
return false;
}
*deletedValue = heap->arr[0]; // 存储根元素的值
heap->arr[0] = heap->arr[heap->size - 1]; // 将最后一个元素移动到根
heap->size--; // 堆大小减1
heapifyDown(heap, 0); // 从根节点向下调整
printf("Deleted Max: %d\n", *deletedValue);
return true;
}
/**
* @brief 查看最大堆的根元素（最大值）
*
* @param heap 指向MaxHeap的指针
* @param peekedValue 用于存储查看到的值的指针
* @return true 查看成功
* @return false 堆为空，查看失败
*/
bool peekMax(MaxHeap* heap, int* peekedValue) {
if (isEmpty(heap)) {
printf("Error: Heap is empty. No max element.\n");
return false;
}
*peekedValue = heap->arr[0];
printf("Peeked Max: %d\n", *peekedValue);
return true;
}
/**
* @brief 打印堆的当前元素（按数组顺序）
* 注意：这只是打印数组内容，不代表堆的树形结构。
*/
void printHeap(MaxHeap* heap) {
printf("Heap elements (array order): [");
for (int i = 0; i < heap->size; i++) {
printf("%d", heap->arr[i]);
if (i < heap->size - 1) {
printf(", ");
}
}
printf("] (Size: %d, Capacity: %d)\n", heap->size, heap->capacity);
}
/**
* @brief 将一个无序数组构建成一个最大堆
* 从最后一个非叶子节点开始，依次向上调整每个节点。
* 时间复杂度：O(n)
*
* @param heap 指向MaxHeap的指针
* @param arr 待构建的原始数组
* @param size 原始数组的大小
* @return true 成功构建
* @return false 原始数组大小超过堆容量
*/
bool buildHeap(MaxHeap* heap, int* arr, int size) {
if (size > heap->capacity) {
printf("Error: Array size (%d) exceeds heap capacity (%d).\n", size, heap->capacity);
return false;
}
for (int i = 0; i < size; i++) {
heap->arr[i] = arr[i];
}
heap->size = size;
// 从最后一个非叶子节点开始向上调整
// 最后一个非叶子节点的索引是 (size / 2) - 1
for (int i = (heap->size / 2) - 1; i >= 0; i--) {
heapifyDown(heap, i);
}
printf("Heap built from array. \n");
return true;
}
// -----------------------------------------------------------
// 4. 主函数进行测试
// -----------------------------------------------------------
int main() {
MaxHeap* myHeap = createMaxHeap(10); // 创建一个容量为10的堆
// 插入操作测试
insert(myHeap, 30);
insert(myHeap, 10);
insert(myHeap, 50);
insert(myHeap, 20);
insert(myHeap, 40);
printHeap(myHeap); // 期望: [50, 40, 30, 10, 20] (或其他有效堆排列)
// 查看最大值测试
int maxVal;
peekMax(myHeap, &maxVal); // 期望: 50
// 删除操作测试
deleteMax(myHeap, &maxVal); // 期望: 删除 50
printHeap(myHeap); // 期望: [40, 20, 30, 10] (或其他有效堆排列)
deleteMax(myHeap, &maxVal); // 期望: 删除 40
printHeap(myHeap); // 期望: [30, 20, 10] (或其他有效堆排列)
// 插入更多元素直到满
insert(myHeap, 60);
insert(myHeap, 70);
insert(myHeap, 5);
insert(myHeap, 90);
insert(myHeap, 80);
insert(myHeap, 100);
insert(myHeap, 15);
printHeap(myHeap); // 期望: 堆满，10个元素
// 尝试插入超出容量
insert(myHeap, 101); // 期望: 插入失败提示
// 从数组建堆测试
MaxHeap* anotherHeap = createMaxHeap(8);
int arr[] = {3, 9, 2, 8, 1, 6, 7, 5};
int n = sizeof(arr) / sizeof(arr[0]);
printf("\nBuilding heap from array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
buildHeap(anotherHeap, arr, n);
printHeap(anotherHeap); // 期望: [9, 8, 7, 5, 1, 6, 2, 3] (或其他有效堆排列)
deleteMax(anotherHeap, &maxVal);
printHeap(anotherHeap);
// 释放内存
destroyMaxHeap(myHeap);
destroyMaxHeap(anotherHeap);
return 0;
}
代码解释：
MaxHeap结构体：arr: 指向存储堆元素的动态数组。capacity: 数组的最大容量。size: 堆中当前元素的数量，也是下一个要插入元素的索引。
辅助函数：
swap(): 简单的值交换函数。getParentIndex(),getLeftChildIndex(),ietRightChildIndex(): 根据数组索引计算父子节点索引。hasLeftChild(),hasRightChild(): 判断一个节点是否有对应的子节点，防止越界。isEmpty(),isFull(): 检查堆的状态。
核心堆操作：
createMaxHeap()/destroyMaxHeap(): 堆的内存分配与释放。heapifyUp(index)(向上调整):当新元素插入到堆的末尾时，它可能比其父节点大，违反了最大堆性质。
heapifyUp将该元素与其父节点比较，如果大于父节点则交换位置。这个过程持续向上，直到元素回到正确位置（不大于父节点）或到达根节点。
时间复杂度： O(log N)，N 是堆的大小（因为每次操作向上移动一层）。
heapifyDown(index)(向下调整):当删除根节点（最大元素）后，或在建堆过程中，根节点被替换为最后一个元素，可能比其子节点小。
heapifyDown将当前节点与其左右子节点比较，找出最大的子节点。如果当前节点小于最大的子节点，则与最大的子节点交换位置，然后对交换后的子节点位置递归调用
heapifyDown。这个过程持续向下，直到元素回到正确位置（不小于任何子节点）或到达叶子节点。
时间复杂度： O(log N)。
insert(value):将新元素添加到数组的末尾（
heap->arr[heap->size]）。heap->size增加。调用
heapifyUp从新元素的位置向上调整，恢复堆性质。时间复杂度： O(log N)。
deleteMax(deletedValue):如果堆为空，返回失败。
保存根节点的值（
heap->arr[0]）作为返回值。将数组的最后一个元素移动到根节点位置（
heap->arr[0] = heap->arr[heap->size - 1]）。heap->size减少。调用
heapifyDown从根节点位置向下调整，恢复堆性质。时间复杂度： O(log N)。
peekMax(): 返回根元素的值，不删除。buildHeap(arr, size)(建堆):将给定数组的元素直接复制到堆的内部数组中。
从最后一个非叶子节点开始（索引为
(size / 2) - 1），向上遍历到根节点。对每个非叶子节点调用
heapifyDown，确保其子树满足堆性质。时间复杂度： O(N)。这比 N 次
insert操作（O(N log N)）更高效。