什么是堆（Heap）？

堆是一种特殊的树形数据结构，它满足以下两个主要属性：

1. 结构性（完全二叉树）：

   • 堆总是一个完全二叉树 (Complete Binary Tree)。这意味着，除了最后一层，所有的层都是完全填充的，并且最后一层的所有节点都尽可能地向左填充。

   • 这个特性使得堆非常适合用数组来表示，因为节点之间的父子关系可以通过索引轻松计算。

2. 堆序性（Heap Property）：

   • 最大堆（Max-Heap）： 在一个最大堆中，每个父节点的值都大于或等于其子节点的值。这意味着，根节点是整个堆中的最大元素。

   • 最小堆（Min-Heap）： 在一个最小堆中，每个父节点的值都小于或等于其子节点的值。这意味着，根节点是整个堆中的最小元素。

总结： 堆是一个用数组实现的完全二叉树，并且满足特定的堆序性（父节点大于等于子节点或小于等于子节点）。

堆的ADT（抽象数据类型）操作

一个典型的堆通常支持以下操作：

1. createHeap(capacity): 创建一个指定容量的空堆。

2. isFull(heap): 检查堆是否已满。

3. isEmpty(heap): 检查堆是否为空。

4. insert(heap, value): 将新元素插入堆中，并保持堆的性质。

5. deleteMax(heap) / deleteMin(heap): 删除堆中最大/最小元素（通常是根节点），并保持堆的性质。

6. peekMax(heap) / peekMin(heap): 查看堆中最大/最小元素（根节点），但不删除。

7. heapifyUp(heap, index): 向上调整堆，当子节点的值发生变化（通常是插入操作后）。

8. heapifyDown(heap, index): 向下调整堆，当父节点的值发生变化（通常是删除操作或建堆操作后）。

9. 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 memoryexit(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++;                 // 堆大小加1heapifyUp(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--;                            // 堆大小减1heapifyDown(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) - 1for (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); // 期望: 删除 50printHeap(myHeap); // 期望: [40, 20, 30, 10] (或其他有效堆排列)deleteMax(myHeap, &maxVal); // 期望: 删除 40printHeap(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;
}

代码解释：

1. MaxHeap 结构体：

   • arr: 指向存储堆元素的动态数组。

   • capacity: 数组的最大容量。

   • size: 堆中当前元素的数量，也是下一个要插入元素的索引。

2. 辅助函数：

   • swap(): 简单的值交换函数。

   • getParentIndex(), getLeftChildIndex(), ietRightChildIndex(): 根据数组索引计算父子节点索引。

   • hasLeftChild(), hasRightChild(): 判断一个节点是否有对应的子节点，防止越界。

   • isEmpty(), isFull(): 检查堆的状态。

3. 核心堆操作：

   • 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)）更高效。