跳到主要内容 数据结构基础：堆的概念与实现 | 极客日志
C 算法
数据结构基础：堆的概念与实现 本文详细介绍了堆的数据结构定义、性质及完全二叉树存储方式。涵盖了堆的初始化、销毁、插入、删除、上下调整等核心接口实现，并对比了向上建堆与向下建堆的排序效率差异。通过 C 语言代码示例展示了最大堆的操作逻辑，帮助读者掌握堆排序算法原理。
接口猎人 发布于 2026/3/29 更新于 2026/4/13 1.堆的概念及结构
如果有一个关键码的集合 K = { k0, k1, k2，…，kn-1 }，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：Ki <= K2i+1 且 Ki <= K2 i+2 (或 Ki >= K2i+1 且 Ki >= K2 i+2)，i = 0, 1, 2…，则称为小堆 (或大堆)。将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆。
堆的性质：
堆中某个结点的值总是不大于或不小于其父结点的值
堆总是一棵完全二叉树
堆的结构：
typedef int HPDataType;
typedef struct Heap {int size;
int capacity;
} HP;
堆的本质就是一个动态数组，把数组以堆的形式呈现出来而已，所以在实现堆的功能时要多画图来帮助理解。
2.堆的接口实现
2.1 堆的初始化
void HeapInit (HP* php) {
assert(php);
php->a = (HPDataType*)malloc (sizeof (HPDataType) * 4 );
if (php->a == NULL ) {
perror("malloc fail" );
return ;
}
php->size = 0 ;
php->capacity = 4 ;
}
熟悉的初始化配方：
判断是否为空指针
创建空间，注意是否会因为开辟失败造成空指针
初始化变量 size 和 capacity
值得注意的是：参数的指针浅拷贝，指向同一块空间，能够改变该空间里的内容，不涉及改变原空间的地址，所以传一级指针即可。
2.2 堆的销毁
void HeapDestroy (HP* php) {
assert(php);
free (php->a);
php->a = NULL ;
php->capacity = php->size = 0 ;
}
2.3 堆的交换
void Swap (HPDataType* p1, HPDataType* p2) {
HPDataType tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
微信扫一扫，关注极客日志 微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
相关免费在线工具 加密/解密文本 使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
Base64 字符串编码/解码 将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
Base64 文件转换器 将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
Markdown 转 HTML 将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
HTML 转 Markdown 将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
JSON 压缩 通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online
因为在堆调整中涉及多次的节点交换，所以额外写一个 Swap 交换函数方便使用。
2.4 堆的向上调整 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 ;
}
}
}
向上调整通常用于最大堆的调整。当向最大堆中插入一个新元素时，新元素会被放置在堆的末尾（即数组的最后一个位置），此时可能会破坏堆的性质（最大堆要求每个节点的值都大于或等于其子节点的值）。通过调用 AdjustUp 函数，可以将新插入的元素上浮到合适的位置，使得整个堆重新满足最大堆的性质。
无论是左节点还是右节点，父亲节点的索引可以通过 (child - 1) / 2 计算得出
while 循环的条件 child > 0 不能写成 child >= 0。当 child 等于 0 时，表示已经到达堆顶，按照 parent = (child - 1) / 2 计算，(-1) / 2 结果为 0（整数除法向下取整），这会导致 parent 和 child 相等，无法向上调整，陷入类似死循环的效果
除了 child 这个数据，前面的数据构成堆，因为向上调整的前提是其他数据都成堆
2.5 堆的插入 void HeapPush (HP* php, HPDataType x) {
assert(php);
if (php->size == php->capacity) {
HPDataType* tmp = (HPDataType*)realloc (php->a, php->capacity * 2 * sizeof (HPDataType));
if (tmp == NULL ) {
perror("realloc fail" );
return ;
}
php->a = tmp;
php->capacity *= 2 ;
}
php->a[php->size] = x;
AdjustUp(php->a, php->size);
php->size++;
}
实现了向上调整，那么插入就很容易了，检查容量是否足够插入，调整新插入的数据也构成堆即可。
值得注意的是：不是 php->capacity * 2，而是 php->capacity * 2 * sizeof(HPDataType)，注意是字节数不是容量数。
2.6 堆的向下调整 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 ;
}
}
}
向下调整通常用于最小堆的调整（这里写的是最大堆的调整）。向下调整的前提是左右子树都必须是大堆或者小堆。
必须把大的那个孩子往上调，保证大堆的性质
这里假设子节点中的左孩子 child = parent * 2 + 1 是子节点中最大的
child + 1 < n && a[child + 1] > a[child] 的目的是判断是否存在右子节点，如果存在，再判断左子节点是否大于右子节点，如果大于就交换
不能写成 a[child + 1] > a[child] && child + 1 < n，要先判断是否存在再访问，不然就非法越界了
2.7 堆的删除 在写堆删除代码前，我们要思考一个问题：为什么不用像之前顺序表那样常用的删除方法——后一个覆盖前一个？
比如一个数组 {42, 12, 18, 4, 2, 3}。
如果采用后一个覆盖前一个的方法删除节点：
向下调整的效率是 O(log n)，后一个覆盖前一个的效率是 O(n)，假设需要挪动 100 万次，那么向下调整只需最多 20 次就能解决，这效率翻得可不止一倍两倍
后一个覆盖前一个之后父子关系全乱，无法进行堆调整
删除堆通常是删除堆顶的数据，将堆顶的数据和最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。
那么为什么是采用最后一个叶节点和根节点交换？
画图可以发现这种交换方式，不会太大程度上破坏堆的结构，保证能够进行向下调整来恢复堆的秩序。
值得注意的是：删除特定位置元素的方法和删除堆顶是一样的。
遍历整个堆来找到目标元素位置
将目标位置的元素与堆的最后一个元素进行交换
根据交换后该元素的值与周围元素的大小关系，决定是进行上浮操作还是下沉操作来恢复堆的性质
void HeapPop (HP* php) {
assert(php);
assert(!HeapEmpty(php));
Swap(&php->a[0 ], &php->a[php->size - 1 ]);
php->size--;
AdjustDown(php->a, php->size, 0 );
}
2.8 堆顶获取 HPDataType HeapTop (HP* php) {
assert(php);
return php->a[0 ];
}
返回堆顶元素的值，最大堆的堆顶元素是堆中的最大值，最小堆的堆顶元素是堆中的最小值。
2.9 堆的判空 bool HeapEmpty (HP* php) {
assert(php);
return php->size == 0 ;
}
如果 php->size 等于 0，说明堆中没有元素，函数返回 true；否则返回 false。
2.10 堆的节点个数 int HeapSize (HP* php) {
assert(php);
return php->size;
}
设置一个返回 size 的函数方便获取堆的节点个数，否则获取 size 只能通过遍历。
2.11 堆的打印 void HeapPrint (HP* php) {
int i;
for (i = 0 ; i < php->size; ++i) {
printf ("%d " , php->a[i]);
}
printf ("\n" );
}
2.12 堆的排序（向上建堆） 既然堆有调整大小顺序的性质，那么就可以据此实现排序的功能。我们知道无论是向上调整，还是向下调整，都要基于一个具有完整性质的堆下来实现，分为向上建堆和向下建堆。
向上建堆：
向上建堆的核心思想是逐个插入元素到堆中，每插入一个元素就对其进行向上调整操作，使其满足堆的性质。具体来说，从数组的第一个元素开始，依次将每个元素插入到已经构建好的部分堆中，然后通过上浮操作将该元素调整到合适的位置，确保整个数组始终保持堆的性质。其实就是对堆插入的模拟实现。
建好堆之后，就能对堆进行排序，排序分为升序和降序。
为什么排序是这样建堆呢？
假设我们要实现升序，如果是建小堆的话，最小值就放在最上面不能动了，剩下的数如果想排序那又得看成一个堆，但是这样父子关系全乱了，因此每排好一个数就要重新建堆，那么效率就太低了。
实现升序就要考虑建大堆，然后再模拟堆删除的方式，不断把大的值调到最下面，最上面小的值通过向下调整，把堆调整为正常的大堆，保证左右子树都是大堆。此时最大的值又在最顶上，--end，和倒数第二个节点交换，重复上面的操作，循环往复就能实现排序。
void HeapSort (HPDataType* a, int n) {
for (int i = 0 ; i < n; ++i) {
AdjustUp(a, i);
}
int end = n - 1 ;
while (end > 0 ) {
Swap(&a[end], &a[0 ]);
AdjustDown(a, end, 0 );
--end;
}
}
2.13 堆的排序（向下建堆） 向下建堆：
向下建堆的过程可以看作是一种分治策略，将一个大问题分解为多个小问题。向下建堆的核心思想是从最后一个非叶子节点开始，依次对每个非叶子节点进行向下调整（下沉）操作，使得以该节点为根的子树满足堆的性质，最终整个数组构成一个堆。简单来说就是对下面每一个小堆依次调整，最终整体就形成了一个大堆。
假设有个数组 {2, 1, 5, 7, 6, 8, 0, 9, 4, 3}，要实现升序建大堆。
先从 6 这个堆开始调整
然后按数组顺序往前推，调整 7 这个堆
依次往前推对每个堆调整，最终就建成了一个大堆
void HeapSort (HPDataType* a, int n) {
for (int i = (n - 1 - 1 ) / 2 ; i >= 0 ; --i) {
AdjustDown(a, n, i);
}
int end = n - 1 ;
while (end > 0 ) {
Swap(&a[end], &a[0 ]);
AdjustDown(a, end, 0 );
--end;
}
}
3.堆排序效率比较 向下建堆：
因此：向下建堆的时间复杂度为 O(N)
用同样的方法，也能算出向上建堆的时间复杂度为 O(N * log N)
所以下向建堆是更高效的
4.代码展示
4.1 Heap.h #pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
typedef int HPDataType;
typedef struct Heap {int size;
int capacity;
} HP;
void HeapInit (HP* php) ;
void HeapDestroy (HP* php) ;
void Swap (HPDataType* p1, HPDataType* p2) ;
void AdjustUp (HPDataType* a, int child) ;
void AdjustDown (HPDataType* a, int n, int parent) ;
void HeapPush (HP* php, HPDataType x) ;
void HeapPop (HP* php) ;
HPDataType HeapTop (HP* php) ;
bool HeapEmpty (HP* php) ;
int HeapSize (HP* php) ;
void HeapPrint (HP* php) ;
void HeapSort (HPDataType* a, int n) ;
4.2 Heap.c #define _CRT_SECURE_NO_WARNINGS
#include "Heap.h"
void HeapInit (HP* php) {
assert(php);
php->a = (HPDataType*)malloc (sizeof (HPDataType) * 4 );
if (php->a == NULL ) {
perror("malloc fail" );
return ;
}
php->size = 0 ;
php->capacity = 4 ;
}
void HeapDestroy (HP* php) {
assert(php);
free (php->a);
php->a = NULL ;
php->capacity = php->size = 0 ;
}
void Swap (HPDataType* p1, HPDataType* p2) {
HPDataType tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
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 HeapPush (HP* php, HPDataType x) {
assert(php);
if (php->size == php->capacity) {
HPDataType* tmp = (HPDataType*)realloc (php->a, php->capacity * 2 * sizeof (HPDataType));
if (tmp == NULL ) {
perror("realloc fail" );
return ;
}
php->a = tmp;
php->capacity *= 2 ;
}
php->a[php->size] = x;
AdjustUp(php->a, php->size);
php->size++;
}
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 HeapPop (HP* php) {
assert(php);
assert(!HeapEmpty(php));
Swap(&php->a[0 ], &php->a[php->size - 1 ]);
php->size--;
AdjustDown(php->a, php->size, 0 );
}
HPDataType HeapTop (HP* php) {
assert(php);
return php->a[0 ];
}
bool HeapEmpty (HP* php) {
assert(php);
return php->size == 0 ;
}
int HeapSize (HP* php) {
assert(php);
return php->size;
}
void HeapPrint (HP* php) {
int i;
for (i = 0 ; i < php->size; ++i) {
printf ("%d " , php->a[i]);
}
printf ("\n" );
}
void HeapSort (HPDataType* a, int n) {
for (int i = 0 ; i < n; ++i) {
AdjustUp(a, i);
}
int end = n - 1 ;
while (end > 0 ) {
Swap(&a[end], &a[0 ]);
AdjustDown(a, end, 0 );
--end;
}
}
