前言
堆（Heap） 是一种特殊的完全二叉树，它是对"优先级"这一概念的经典数据抽象。生活中处处有"优先级"——医院急诊按病情紧急程度处理患者，操作系统按优先级调度进程，任务队列按紧急程度排期……堆正是为这类场景量身定做的数据结构。
堆的核心特征可以用一句话概括：堆中每个节点的值都大于等于（或小于等于）其子节点的值。在这个约束下，堆的根节点总是"最值"——要么最大（大顶堆），要么最小（小顶堆）。这使得堆成为实现优先队列的天然选择。
本文将用 C 语言 逐步实现大顶堆（Max Heap）和小顶堆（Min Heap），涵盖初始化、插入、删除、堆排序等核心操作，代码按功能拆分为独立模块。
目录
一、基本概念
1.堆的定义
堆是一棵完全二叉树，且满足以下条件之一：
- 大顶堆（Max Heap）：每个节点的值 ≥ 其左右孩子的值
- 小顶堆（Min Heap）：每个节点的值 ≤ 其左右孩子的值
因为堆是完全二叉树，所以天然适合用数组存储（无需指针），这也是堆最高效的地方。
2.数组存储的父子关系
对于数组中下标为 i 的节点（从 0 开始）：
| 关系 | 公式 |
|---|---|
| 父节点下标 | (i - 1) / 2 |
| 左孩子下标 | 2 * i + 1 |
| 右孩子下标 | 2 * i + 2 |
| 最后一个非叶子节点 | (n - 2) / 2 （n 为数组长度） |
数组表示：[50, 30, 40, 10, 20, 35]
对应的大顶堆：
50(0)
/ \
30(1) 40(2)
/ \ /
10(3) 20(4) 35(5)
3.两种堆的图示
大顶堆（Max Heap） 小顶堆（Min Heap）
90 10
/ \ / \
70 80 20 30
/ \ / / \ /
50 40 60 40 50 60
二、堆的核心操作及时间复杂度
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 建堆（Heapify） | O(n) | 从无序数组构建堆 |
| 插入（Push） | O(log n) | 在堆尾插入，向上调整 |
| 删除堆顶（Pop） | O(log n) | 删除根，末尾补上，向下调整 |
| 获取堆顶（Top） | O(1) | 直接返回 arr[0] |
| 堆排序 | O(n log n) | 反复 Pop 堆顶 |
三、代码模块实现（以大顶堆为例）
头文件和宏定义
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h> // 使用 bool 类型
#define INIT_CAPACITY 16 // 初始容量
#define MAX(a, b) ((a) > (b) ? (a) : (b))1.堆的结构定义
/**
* 大顶堆结构定义
* 底层用动态数组存储
*/
typedef struct MaxHeap {
int *data; // 存储堆元素的数组
int size; // 当前元素个数
int capacity; // 数组总容量
} MaxHeap;2.初始化与销毁
/**
* 创建并初始化一个大顶堆
* @return 指向堆的指针
*/
MaxHeap* createMaxHeap() {
MaxHeap *heap = (MaxHeap*)malloc(sizeof(MaxHeap));
if (heap == NULL) {
printf("内存分配失败！\n");
exit(1);
}
heap->data = (int*)malloc(sizeof(int) * INIT_CAPACITY);
if (heap->data == NULL) {
printf("内存分配失败！\n");
exit(1);
}
heap->size = 0;
heap->capacity = INIT_CAPACITY;
return heap;
}
/**
* 销毁堆，释放内存
* @param heap 指向堆的指针（二级指针，释放后置空）
*/
void destroyMaxHeap(MaxHeap **heap) {
if (*heap == NULL) return;
free((*heap)->data);
free(*heap);
*heap = NULL;
}3.辅助函数——交换 & 扩容
/**
* 交换两个整数的值
*/
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
/**
* 当数组容量不足时，自动扩容为原来的 2 倍
*/
void ensureCapacity(MaxHeap *heap) {
if (heap->size < heap->capacity) {
return; // 容量足够，无需扩容
}
heap->capacity *= 2;
heap->data = (int*)realloc(heap->data, sizeof(int) * heap->capacity);
if (heap->data == NULL) {
printf("内存扩容失败！\n");
exit(1);
}
printf("扩容完成，当前容量：%d\n", heap->capacity);
}4.向上调整（核心操作之一）
向上调整用于插入操作。当新元素被放到堆尾时，它可能"以下犯上"——比父节点还大。这时需要让它不断"上浮"，直到找到合适的位置。
/**
* 向上调整（上浮）
* 从下标 index 开始，沿父节点路径向上比较并交换
* 直到满足大顶堆性质：父节点 >= 子节点
* @param heap 堆指针
* @param index 起始调整位置（通常是堆尾）
*/
void siftUp(MaxHeap *heap, int index) {
while (index > 0) {
int parentIdx = (index - 1) / 2;
// 如果当前节点 <= 父节点，调整结束
if (heap->data[index] <= heap->data[parentIdx]) {
break;
}
// 否则与父节点交换，继续上浮
swap(&heap->data[index], &heap->data[parentIdx]);
index = parentIdx;
}
}图解上浮过程（插入 80）：
初始堆： 插入 80 到末尾： 上浮调整后：
50 50 80
/ \ / \ / \
30 40 30 40 30 50
/ \ / \ / / \ /
10 20 10 20 80 10 20 30
数组变化：
[50,30,40,10,20] → [50,30,40,10,20,80] → [80,30,50,10,20,40]
↑80>40交换 ↑50<80交换5.向下调整（核心操作之二）
向下调整用于删除堆顶操作。当堆顶被移除、堆尾元素补到根位置时，这个"新根"可能太小，需要让它不断"下沉"到正确位置。
/**
* 向下调整（下沉）
* 从下标 index 开始，向下与较大的子节点比较并交换
* @param heap 堆指针
* @param index 起始调整位置（通常是堆顶 0）
*/
void siftDown(MaxHeap *heap, int index) {
int size = heap->size;
while (1) {
int leftChild = 2 * index + 1;
int rightChild = 2 * index + 2;
int largest = index; // 记录"最大者"的下标
// 如果左孩子存在且比当前大
if (leftChild < size && heap->data[leftChild] > heap->data[largest]) {
largest = leftChild;
}
// 如果右孩子存在且比当前最大的还大
if (rightChild < size && heap->data[rightChild] > heap->data[largest]) {
largest = rightChild;
}
// 如果当前节点已经是最大的，调整结束
if (largest == index) {
break;
}
// 否则与较大的子节点交换，继续下沉
swap(&heap->data[index], &heap->data[largest]);
index = largest;
}
}图解下沉过程（删除堆顶 90）：
初始堆： 移除 90，末尾 20 补到堆顶： 下沉调整后：
90 20 70
/ \ / \ / \
70 80 70 80 60 80
/ \ / \ / \
60 50 60 50 20 50
数组：[90,70,80,60,50] → [20,70,80,60,50] → [80,70,20,60,50]
↑20<70和80，与80交换 ↑20<70和50，与70交换
6.插入元素（Push）
/**
* 向大顶堆中插入一个元素
* 策略：先放到末尾，再向上调整
* @param heap 堆指针
* @param value 要插入的值
*/
void pushMaxHeap(MaxHeap *heap, int value) {
// 容量检查，必要时扩容
ensureCapacity(heap);
// 将新元素放到数组末尾
heap->data[heap->size] = value;
heap->size++;
// 从新位置开始向上调整
siftUp(heap, heap->size - 1);
}7.删除堆顶（Pop）
/**
* 删除大顶堆的堆顶元素（最大值）
* 策略：堆顶 ← 堆尾，size--，再从顶向下调整
* @param heap 堆指针
* @return 被删除的堆顶值；如果堆为空返回 -1
*/
int popMaxHeap(MaxHeap *heap) {
if (heap->size == 0) {
printf("堆为空，无法删除！\n");
return -1;
}
// 保存堆顶元素（最大值）
int maxValue = heap->data[0];
// 将最后一个元素移到堆顶
heap->data[0] = heap->data[heap->size - 1];
heap->size--;
// 从堆顶开始向下调整
siftDown(heap, 0);
return maxValue;
}8.获取堆顶
/**
* 获取堆顶元素（不删除）
* @param heap 堆指针
* @return 堆顶值；堆为空返回 -1
*/
int topMaxHeap(MaxHeap *heap) {
if (heap->size == 0) {
printf("堆为空！\n");
return -1;
}
return heap->data[0];
}9.从数组建堆（Heapify）
给定一个无序数组，如何在 O(n) 时间内将其调整为堆？秘诀是从最后一个非叶子节点开始，逐个向下调整。
/**
* 从无序数组构建大顶堆（Heapify）
* 时间复杂度 O(n)
* @param heap 堆指针（data 已赋值、size 已设置）
*/
void buildMaxHeap(MaxHeap *heap) {
// 从最后一个非叶子节点开始，逐个下沉
// 最后一个非叶子节点下标 = (size - 2) / 2
for (int i = (heap->size - 2) / 2; i >= 0; i--) {
siftDown(heap, i);
}
}为什么从 (n-2)/2 开始？ 因为叶子节点（下标 > (n-2)/2 的节点）没有子节点，不需要下沉。
O(n) 的直观理解：虽然外层循环是 O(n / 2)，但每个节点的下沉高度不同——底层节点多但下沉距离短，顶层节点少但下沉距离长。严格推导下来，总时间是 O(n)。
10.堆排序
堆排序的思路极其优雅：
- 建堆：将无序数组调整为大顶堆
- 排序：反复将堆顶（最大值）与堆尾交换，然后对新的堆顶做下沉调整
经过这两步，数组就变成了升序排列。
/**
* 堆排序（原地排序，升序）
* 将数组 arr 的前 n 个元素按升序排列
* @param arr 待排序数组
* @param n 数组长度
*/
void heapSort(int arr[], int n) {
// 第一步：原地建堆
// 从最后一个非叶子节点开始向下调整
for (int i = (n - 2) / 2; i >= 0; i--) {
int index = i;
while (1) {
int left = 2 * index + 1;
int right = 2 * index + 2;
int largest = index;
if (left < n && arr[left] > arr[largest]) largest = left;
if (right < n && arr[right] > arr[largest]) largest = right;
if (largest == index) break;
swap(&arr[index], &arr[largest]);
index = largest;
}
}
// 第二步：依次将堆顶移到末尾
for (int i = n - 1; i > 0; i--) {
// 将堆顶（最大值）换到数组末尾
swap(&arr[0], &arr[i]);
// 对新的堆顶做下沉调整，堆的范围缩小为 [0, i)
int index = 0;
while (1) {
int left = 2 * index + 1;
int right = 2 * index + 2;
int largest = index;
if (left < i && arr[left] > arr[largest]) largest = left;
if (right < i && arr[right] > arr[largest]) largest = right;
if (largest == index) break;
swap(&arr[index], &arr[largest]);
index = largest;
}
}
}堆排序执行过程图解（数组 [50, 20, 40, 10, 30, 35]）：
原始数组： [50, 20, 40, 10, 30, 35]
Step 1 - 建堆： [50, 30, 40, 10, 20, 35]
50
/ \
30 40
/ \ /
10 20 35
Step 2 - 排序：
交换 50↔35 → 下沉 → [40, 30, 35, 10, 20, | 50]
交换 40↔20 → 下沉 → [35, 30, 20, 10, | 40, 50]
交换 35↔10 → 下沉 → [30, 10, 20, | 35, 40, 50]
交换 30↔20 → 下沉 → [20, 10, | 30, 35, 40, 50]
交换 20↔10 → → [10, 20, 30, 35, 40, 50] ✅
11.打印堆
/**
* 以数组形式打印堆的内容
*/
void printMaxHeap(MaxHeap *heap) {
printf("堆：[");
for (int i = 0; i < heap->size; i++) {
printf("%d", heap->data[i]);
if (i < heap->size - 1) printf(", ");
}
printf("] (size=%d, capacity=%d)\n", heap->size, heap->capacity);
}12.扩展——小顶堆
只需将 siftUp 和 siftDown 中的比较符号反转，大顶堆就变成了小顶堆。
这里直接给出小顶堆的完整结构定义和核心调整函数：
// ---------- 小顶堆结构 ----------
typedef struct MinHeap {
int *data;
int size;
int capacity;
} MinHeap;
MinHeap* createMinHeap() {
MinHeap *heap = (MinHeap*)malloc(sizeof(MinHeap));
heap->data = (int*)malloc(sizeof(int) * INIT_CAPACITY);
heap->size = 0;
heap->capacity = INIT_CAPACITY;
return heap;
}
// ---------- 小顶堆向上调整（与上浮相反——小的往上浮） ----------
void minSiftUp(MinHeap *heap, int index) {
while (index > 0) {
int parentIdx = (index - 1) / 2;
// 关键区别：当前节点 >= 父节点时停止（小顶堆要求父 <= 子）
if (heap->data[index] >= heap->data[parentIdx]) break;
swap(&heap->data[index], &heap->data[parentIdx]);
index = parentIdx;
}
}
// ---------- 小顶堆向下调整（小的往上浮，大的往下沉） ----------
void minSiftDown(MinHeap *heap, int index) {
int size = heap->size;
while (1) {
int left = 2 * index + 1;
int right = 2 * index + 2;
int smallest = index;
// 关键区别：找最小的孩子，而不是最大的
if (left < size && heap->data[left] < heap->data[smallest]) smallest = left;
if (right < size && heap->data[right] < heap->data[smallest]) smallest = right;
if (smallest == index) break;
swap(&heap->data[index], &heap->data[smallest]);
index = smallest;
}
}
// 小顶堆插入
void pushMinHeap(MinHeap *heap, int value) {
if (heap->size == heap->capacity) {
heap->capacity *= 2;
heap->data = (int*)realloc(heap->data, sizeof(int) * heap->capacity);
}
heap->data[heap->size] = value;
heap->size++;
minSiftUp(heap, heap->size - 1);
}
// 小顶堆删除堆顶
int popMinHeap(MinHeap *heap) {
if (heap->size == 0) return -1;
int minValue = heap->data[0];
heap->data[0] = heap->data[heap->size - 1];
heap->size--;
minSiftDown(heap, 0);
return minValue;
}13.主函数测试
int main()
{
printf("===== 大顶堆测试 =====\n");
MaxHeap *maxHeap = createMaxHeap();
// 插入测试
int values[] = {50, 20, 40, 10, 30, 35, 80};
int n = sizeof(values) / sizeof(values[0]);
printf("依次插入：");
for (int i = 0; i < n; i++) {
printf("%d ", values[i]);
pushMaxHeap(maxHeap, values[i]);
}
printf("\n");
printMaxHeap(maxHeap);
printf("堆顶元素：%d\n\n", topMaxHeap(maxHeap));
// 删除测试
printf("依次删除堆顶：");
int count = maxHeap->size;
for (int i = 0; i < count; i++) {
printf("%d ", popMaxHeap(maxHeap));
}
printf("\n");
printMaxHeap(maxHeap);
// 从数组建堆测试
printf("\n===== 从数组建堆测试 =====\n");
int arr[] = {10, 30, 5, 60, 20, 40, 15, 50};
int arrSize = sizeof(arr) / sizeof(arr[0]);
printf("原始数组：");
for (int i = 0; i < arrSize; i++) printf("%d ", arr[i]);
printf("\n");
MaxHeap *heapFromArr = createMaxHeap();
// 直接复制数据
free(heapFromArr->data);
heapFromArr->data = (int*)malloc(sizeof(int) * arrSize);
for (int i = 0; i < arrSize; i++) heapFromArr->data[i] = arr[i];
heapFromArr->size = arrSize;
heapFromArr->capacity = arrSize;
buildMaxHeap(heapFromArr);
printf("建堆结果：");
printMaxHeap(heapFromArr);
destroyMaxHeap(&heapFromArr);
// 堆排序测试
printf("\n===== 堆排序测试 =====\n");
int sortArr[] = {42, 15, 8, 23, 4, 16, 30, 11, 50, 3};
int sortSize = sizeof(sortArr) / sizeof(sortArr[0]);
printf("排序前：");
for (int i = 0; i < sortSize; i++) printf("%d ", sortArr[i]);
printf("\n");
heapSort(sortArr, sortSize);
printf("排序后：");
for (int i = 0; i < sortSize; i++) printf("%d ", sortArr[i]);
printf("\n");
// 小顶堆测试
printf("\n===== 小顶堆测试 =====\n");
MinHeap *minHeap = createMinHeap();
int minVals[] = {30, 10, 50, 20, 40, 5};
for (int i = 0; i < 6; i++) pushMinHeap(minHeap, minVals[i]);
printf("依次删除堆顶（应从小到大）：");
int mc = minHeap->size;
for (int i = 0; i < mc; i++) printf("%d ", popMinHeap(minHeap));
printf("\n");
// 释放内存
destroyMaxHeap(&maxHeap);
free(minHeap->data);
free(minHeap);
if (maxHeap == NULL) {
printf("\n所有内存已释放！\n");
}
return 0;
}五、完整程序运行效果
===== 大顶堆测试 =====
依次插入：50 20 40 10 30 35 80
扩容完成，当前容量：32
堆：[80, 30, 50, 10, 20, 35, 40] (size=7, capacity=32)
堆顶元素：80
依次删除堆顶：80 50 40 35 30 20 10
堆：[] (size=0, capacity=32)
===== 从数组建堆测试 =====
原始数组：10 30 5 60 20 40 15 50
建堆结果：[60, 50, 40, 30, 20, 5, 15, 10] (size=8, capacity=8)
===== 堆排序测试 =====
排序前：42 15 8 23 4 16 30 11 50 3
排序后：3 4 8 11 15 16 23 30 42 50
===== 小顶堆测试 =====
依次删除堆顶（应从小到大）：5 10 20 30 40 50
所有内存已释放！
六、堆的经典应用场景
1. Top K 问题
在海量数据中找出最大的 K 个元素。用小顶堆维护一个大小为 K 的窗口：
- 遍历数据，堆未满时直接入堆
- 堆满后，如果当前元素 > 堆顶，则替换堆顶并下沉
/**
* 找出数组中最大的 K 个元素
* 使用小顶堆实现，时间复杂度 O(n log K)
*/
int* topK(int arr[], int n, int k, int *resultSize) {
if (k <= 0 || n <= 0) {
*resultSize = 0;
return NULL;
}
// 建立大小为 k 的小顶堆
MinHeap *heap = createMinHeap();
for (int i = 0; i < n; i++) {
if (heap->size < k) {
pushMinHeap(heap, arr[i]);
} else if (arr[i] > heap->data[0]) {
popMinHeap(heap);
pushMinHeap(heap, arr[i]);
}
}
// 导出结果
*resultSize = heap->size;
int *result = (int*)malloc(sizeof(int) * heap->size);
for (int i = 0; i < heap->size; i++) {
result[i] = heap->data[i];
}
free(heap->data);
free(heap);
return result;
}2. 数据流中位数
用两个堆——一个大顶堆存较小的一半，一个小顶堆存较大的一半——动态维护中位数：
大顶堆（存小的一半） 小顶堆（存大的一半）
[5] [6]
[3] [8]
[1] [9]
中位数 = (大顶堆堆顶 + 小顶堆堆顶) / 2 （偶数个时）
= 大顶堆堆顶 （奇数个时）
七、总结
以上就是堆的全部内容。上浮、下沉是堆的灵魂，建堆、堆排序、TopK 都是面试高频考点。代码建议手动敲一遍加深理解，有疑问欢迎评论区交流，如果本文对你有帮助，欢迎点赞收藏！
转载自 CSDN-专业IT技术社区
原文链接：https://blog.csdn.net/2502_94387000/article/details/163147806
