跳到主要内容 数据结构:堆的概念与 C 语言实现 | 极客日志
C 算法
数据结构:堆的概念与 C 语言实现 堆这种数据结构的基本概念,包括大堆与小堆的定义及特点。文章详细阐述了使用数组实现小堆的思路,涵盖初始化、销毁、插入(入堆)、删除(出堆)、获取堆顶等核心操作,并提供了完整的 C 语言代码示例,帮助读者理解堆的调整算法及内存管理。
刀狂 发布于 2026/3/28 更新于 2026/4/16 2 浏览一、堆是什么?
1. 堆的定义
堆:
堆是一种特殊的完全二叉树,在此基础上增加了一些有序性约束。
2. 堆的分类
堆从排序的角度,被分为两类:大堆和小堆。
大堆
在大堆中,任何一个父结点的值都要大于或等于子结点的值(只是父亲与孩子之间的比较,与兄弟结点无关)。
如图,这就是一个大堆:
小堆
而在小堆中恰恰相反,任何一个子结点的值都要大于或等于父结点的值(只是父亲与孩子之间的比较,与兄弟结点无关)。
如图,这就是一个小堆:
3. 堆的特点
由于在大堆中,任何一个父结点的值都要大于或等于子结点的值;在小堆中,任何一个子结点的值都要大于或等于父结点的值。故堆有一个很重要的特点:在堆中,根结点的值最大或最小,故可通过堆来找极大值和极小值。
二、堆的实现(小堆)
(本文实现的堆是小堆,但原理一样)
1. 用什么来实现?
之前,我们讲了完全二叉树的存储,提到完全二叉树的编号是连续的。对于完全二叉树来说,我们可以用数组来进行存储,用下标来进行编号。而堆,就是一个完全二叉树,所以直接使用数组实现即可。
综上所诉,使用数组的结构来实现堆更优。
2. 实现思路
与顺序表同理,堆的实现也应该有三名成员:
指向一个数组的指针
堆内的总元素
堆内的总容量
3. 代码实现
本文以创建一个 int 类型的堆为例
(1)创建头文件&源文件
在写复杂程序时要养成写多个头文件&源文件的好习惯,这样条理就很清晰也不会乱。
创建了一个 Heap.h 头文件,用于存放函数的声明和一些库函数的头文件。
创建了一个 Heap.c 源文件,用于放函数的定义 (堆的主体)。
还有一个 Test.c 源文件,用于测试实现的堆的运行效果。
(2)定义堆(定义)
首先我们要定义一个堆。
代码演示:(内有注释)
(在头文件 Heap.h 中写)
typedef int HPDataType;
HPDataType* a;
size;
capacity;
} Heap;
微信扫一扫,关注极客日志 微信公众号「极客日志」,在微信中扫描左侧二维码关注。展示文案:极客日志 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 {
HPDataType* a;
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 ;
}