跳到主要内容 数据结构：堆的概念与 C 语言实现 | 极客日志
C 算法
数据结构：堆的概念与 C 语言实现 堆这种数据结构的基本概念，包括大堆与小堆的定义及特点。文章详细阐述了使用数组实现小堆的思路，涵盖初始化、销毁、插入（入堆）、删除（出堆）、获取堆顶等核心操作，并提供了完整的 C 语言代码示例，帮助读者理解堆的调整算法及内存管理。
刀狂 发布于 2026/3/28 更新于 2026/4/16 一、堆是什么？
1. 堆的定义
堆：
堆是一种特殊的完全二叉树，在此基础上增加了一些有序性约束。
2. 堆的分类
堆从排序的角度，被分为两类：大堆和小堆。
大堆
在大堆中，任何一个父结点的值都要大于或等于子结点的值（只是父亲与孩子之间的比较，与兄弟结点无关）。
如图，这就是一个大堆：
小堆
而在小堆中恰恰相反，任何一个子结点的值都要大于或等于父结点的值（只是父亲与孩子之间的比较，与兄弟结点无关）。
如图，这就是一个小堆：
3. 堆的特点
由于在大堆中，任何一个父结点的值都要大于或等于子结点的值；在小堆中，任何一个子结点的值都要大于或等于父结点的值。故堆有一个很重要的特点：在堆中，根结点的值最大或最小，故可通过堆来找极大值和极小值。
二、堆的实现（小堆）
（本文实现的堆是小堆，但原理一样）
1. 用什么来实现？
之前，我们讲了完全二叉树的存储，提到完全二叉树的编号是连续的。对于完全二叉树来说，我们可以用数组来进行存储，用下标来进行编号。而堆，就是一个完全二叉树，所以直接使用数组实现即可。
综上所诉，使用数组的结构来实现堆更优。
2. 实现思路
与顺序表同理，堆的实现也应该有三名成员：
指向一个数组的指针堆内的总元素堆内的总容量
3. 代码实现
本文以创建一个 int 类型的堆为例
（1）创建头文件&源文件
在写复杂程序时要养成写多个头文件&源文件的好习惯，这样条理就很清晰也不会乱。
创建了一个 Heap.h 头文件，用于存放函数的声明和一些库函数的头文件。
创建了一个 Heap.c 源文件，用于放函数的定义 (堆的主体)。
还有一个 Test.c 源文件，用于测试实现的堆的运行效果。
（2）定义堆（定义）
首先我们要定义一个堆。
代码演示：（内有注释）
（在头文件 Heap.h 中写）
typedef int HPDataType;
微信扫一扫，关注极客日志 微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 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
typedef
struct Heap {
int
int
在定义堆的代码中，有两个需要注意的点：
本文是以 int 类型为例，但如果以后要将堆的类型修改成 char 类型或是其他类型一个一个修改就很麻烦。所以我们重定义 int 类型为 HPDataType，并将接下来代码中的 int 类型全部写成 HPDataType。这是为了方便我们以后对类型进行修改，仅需将 int 改为其他类型即可。
在定义堆的同时重定义堆变量名为 Heap 方便以后使用。
（3）堆的初始化（初始化） 定义完堆后，肯定要对堆进行初始化，内容全部置 0 / NULL。
代码演示：（内有注释）
（其中 hp 是一个堆指针类型的指针，下同）
void HeapInit (Heap* hp) {
assert(hp);
hp->a = NULL ;
hp->capacity = 0 ;
hp->size = 0 ;
}
在写堆的实现的代码中，有一个很重要的点：
当我们函数在进行传参时，可能会传入空指针，而我们知道空指针是不能进行解引用的。故为了我们的代码更加健壮，可以加入 assert 断言 来判断是否符合条件，在之后的代码中也都有。
（4）堆的销毁（销毁） 在我们的程序运行完毕后，当然要对堆进行销毁，以免占用内存。
代码演示：（内有注释）
（其中 hp 是一个堆指针类型的指针，下同）
void HeapDestory (Heap* hp) ;
void HeapDestory (Heap* hp) {
assert(hp);
free (hp->a);
hp->a = NULL ;
hp->capacity = 0 ;
hp->size = 0 ;
}
（5）插入数据（入堆）
若一次性开辟的空间过大，可能会造成空间的浪费。
若一次性开辟的空间过小，就可能会导频繁的开辟空间，这样运行的效率就会大大降低。
经过科学研究，发现每次增容 2 倍 & 3 倍 空间最为合适。当原空间为 100 的空间不足时，就增容到 200 空间。（本文选择的是每次增容 2 倍）。
第三步：调整堆
在插入之后，该堆就不一定还是小堆了，故需要做出调整，将尾插的数据向上调整。 那么该怎么调整呢？
由于我们建的是小堆，所以若孩子小于父亲，孩子就要向上调整，将父亲与孩子的值对调。直到父亲小于孩子，调整结束。
代码演示：（内有注释）
（其中 hp 是一个堆指针类型的指针，下同）
void HeapPush (Heap* hp, HPDataType x) ;
void HeapPush (Heap* hp, HPDataType x) {
assert(hp);
if (hp->size == hp->capacity)
{
int newcapacity = hp->capacity == 0 ? 4 : 2 * hp->capacity;
HPDataType* tmp = (HPDataType*)realloc (hp->a, newcapacity * sizeof (HPDataType));
if (tmp == NULL )
{
perror("realloc fail" );
return ;
}
hp->a = tmp;
hp->capacity = newcapacity;
}
hp->a[hp->size] = x;
hp->size++;
AdjustUp(hp->a, hp->size - 1 );
}
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 Swap (HPDataType* x, HPDataType* y) {
HPDataType tmp = *x;
*x = *y;
*y = tmp;
}
（6）删除数据（出堆） 对于堆来说，要删除数据一般都是删除堆顶的元素。但是删除后想要调整回一个小堆就不容易了。所以我们采用一种间接删除的方式。
方法：先将堆顶和堆尾的值交换，然后删除堆尾数据。此时相当于把之前的堆顶数据删除了。而且对于数组来说尾删是很简单的，只需要将总个数减一就行。然后就开始处理首元素了，和尾插同理，需要调整，但这里是向下调整。由于我们建的是小堆，所以若父亲大于孩子，父亲就要向下调整，将父亲与孩子的值对调。直到父亲小于孩子，调整结束。
代码演示：（内有注释）
（其中 hp 是一个堆指针类型的指针，下同）
void HeapPop (Heap* hp) {
assert(hp);
assert(hp->size > 0 );
Swap(&(hp->a[0 ]), &(hp->a[hp->size - 1 ]));
hp->size--;
AdjustDown(hp->a, 0 , hp->size);
}
void AdjustDown (HPDataType* a, int parent, int size) {
int child = 2 * parent + 1 ;
while (child <= size - 1 ) {
if (child + 1 <= size - 1 && a[child + 1 ] < a[child]) {
child++;
}
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = 2 * parent + 1 ;
}
else {
break ;
}
}
}
void Swap (HPDataType* x, HPDataType* y) {
HPDataType tmp = *x;
*x = *y;
*y = tmp;
}
（7）获取堆顶元素 这个很简单，直接用下标进行访问数据，再返回所对应的值。
代码演示：（内有注释）
（其中 hp 是一个堆指针类型的指针，下同）
HPDataType HeapTop (Heap* hp) ;
HPDataType HeapTop (Heap* hp) {
assert(hp);
assert(hp->size > 0 );
return hp->a[0 ];
}
（8）获取堆的数据个数 代码演示：（内有注释）
（其中 hp 是一个堆指针类型的指针，下同）
int HeapSize (Heap* hp) {
assert(hp);
return hp->size;
}
（9）检测堆是否为空 这个很简单，如果堆为空返回非零结果，如果不为空返回 0。
代码演示：（内有注释）
（其中 hp 是一个堆指针类型的指针，下同）
int HeapEmpty (Heap* hp) {
assert(hp);
return hp->size == 0 ;
}
三、完整代码实现
1. Heap.h #pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int HPDataType;
typedef struct Heap {int size;
int capacity;
} Heap;
void HeapInit (Heap* hp) ;
void HeapDestory (Heap* hp) ;
void HeapPush (Heap* hp, HPDataType x) ;
void HeapPop (Heap* hp) ;
HPDataType HeapTop (Heap* hp) ;
int HeapSize (Heap* hp) ;
int HeapEmpty (Heap* hp) ;
2. Heap.c #include "Heap.h"
void HeapInit (Heap* hp) {
assert(hp);
hp->a = NULL ;
hp->capacity = 0 ;
hp->size = 0 ;
}
void HeapDestory (Heap* hp) {
assert(hp);
free (hp->a);
hp->a = NULL ;
hp->capacity = 0 ;
hp->size = 0 ;
}
void Swap (HPDataType* x, HPDataType* y) {
HPDataType tmp = *x;
*x = *y;
*y = 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 (Heap* hp, HPDataType x) {
assert(hp);
if (hp->size == hp->capacity)
{
int newcapacity = hp->capacity == 0 ? 4 : 2 * hp->capacity;
HPDataType* tmp = (HPDataType*)realloc (hp->a, newcapacity * sizeof (HPDataType));
if (tmp == NULL )
{
perror("realloc fail" );
return ;
}
hp->a = tmp;
hp->capacity = newcapacity;
}
hp->a[hp->size] = x;
hp->size++;
AdjustUp(hp->a, hp->size - 1 );
}
void AdjustDown (HPDataType* a, int parent, int size) {
int child = 2 * parent + 1 ;
while (child <= size - 1 ) {
if (child + 1 <= size - 1 && a[child + 1 ] < a[child]) {
child++;
}
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = 2 * parent + 1 ;
}
else {
break ;
}
}
}
void HeapPop (Heap* hp) {
assert(hp);
assert(hp->size > 0 );
Swap(&(hp->a[0 ]), &(hp->a[hp->size - 1 ]));
hp->size--;
AdjustDown(hp->a, 0 , hp->size);
}
HPDataType HeapTop (Heap* hp) {
assert(hp);
assert(hp->size > 0 );
return hp->a[0 ];
}
int HeapSize (Heap* hp) {
assert(hp);
return hp->size;
}
int HeapEmpty (Heap* hp) {
assert(hp);
return hp->size == 0 ;
}
3. Test.c #include "Heap.h"
int main () {
Heap H;
HeapInit(&H);
HeapPush(&H, 423 );
HeapPush(&H, 234 );
HeapPush(&H, 233 );
HeapPush(&H, 44 );
HeapPush(&H, 35 );
HeapPush(&H, 6235 );
while (!HeapEmpty(&H)) {
printf ("%d " , HeapTop(&H));
HeapPop(&H);
}
printf ("\n\n" );
HeapDestory(&H);
return 0 ;
}
