数据结构 堆(2)---堆的实现

上篇文章我们详细介绍了堆和树的基本概念以及它们之间的关系，还要知道一般实现堆的方式是使

用顺序结构的数组进行存储数据及实现。下来我们看看利用顺序结构的数组如何实现对的内容:

1.堆的实现

关于堆的实现，也是三个文件，头文件，实现文件和测试文件。下面我们逐一进行讲解:

1.1 头文件(Heap.h)

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>//堆的结构
typedef int HPDataType;
typedef struct Heap
{HPDataType* arr;int size;     //有效数据个数int capacity; //空间大小
}HP;//交换函数
void Swap(int* x, int* y);
//向上调整函数
void AdjustUp(HPDataType* arr, int child);
//向下调整函数
void AdjustDown(HPDataType* arr, int parent, int n);//初始化函数
void HPInit(HP* php);
//销毁函数
void HPDestroy(HP* php);
//打印函数
void HPPrint(HP* php);//插入函数
void HPPush(HP* php, HPDataType x);
//删除函数
void HPPop(HP* php);
//取堆顶数据
HPDataType HPTop(HP* php);// 判空函数
bool HPEmpty(HP* php);

以下从 头文件作用、各部分代码解析、整体功能梳理 角度，详细介绍这个堆实现的头文件：

1. 头文件基础作用

 #pragma once  是编译器指令，保证头文件 只被编译一次，避免重复包含导致的符号冲突）。

引入的标准库：

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

-  stdio.h ：用于输入输出（如  HPPrint  可能用到  printf  打印堆内容 ）。

-  stdlib.h ：提供内存分配（ malloc / free  ）、数值转换等函数，堆的动态扩容会用到。

-  assert.h ：提供  assert  断言，用于调试时检查关键条件（如指针非空）。

-  stdbool.h ：引入  bool  类型（ true / false  ），让代码语义更清晰。

2. 堆的结构定义（ struct Heap ）

typedef int HPDataType;
typedef struct Heap
{HPDataType* arr;    // 存储堆数据的动态数组int size;           // 堆中有效元素个数（当前堆的大小）int capacity;       // 数组总容量（空间大小，避免频繁扩容）
}HP;

-  HPDataType ：用  typedef  把  int  重命名为  HPDataType ，方便后续修改堆存储的数据类型

（如改成  float /自定义结构体，只需改这里 ）。

-  arr ：动态数组，底层用数组模拟堆结构（完全二叉树按层序存储特性，可通过下标快速找父子

节点 ）。

-  size ：记录当前堆中有多少个元素，决定堆的有效范围。

-  capacity ：记录数组总共能存多少元素， size  超过  capacity  时需要扩容。

3. 函数声明解析（堆的核心操作）

//交换函数
void Swap(int* x, int* y);
//向上调整函数
void AdjustUp(HPDataType* arr, int child);
//向下调整函数
void AdjustDown(HPDataType* arr, int parent, int n);//初始化函数
void HPInit(HP* php);
//销毁函数
void HPDestroy(HP* php);
//打印函数
void HPPrint(HP* php);//插入函数
void HPPush(HP* php, HPDataType x);
//删除函数
void HPPop(HP* php);
//取堆顶数据
HPDataType HPTop(HP* php);// 判空函数
bool HPEmpty(HP* php);

头文件里声明的函数，覆盖了堆的 初始化、销毁、增删查、调整 等功能，是堆的核心接口：

关于这些函数的实现, 我们在下一个实现文件中进行详细解释

 
4. 头文件的整体作用

这个头文件是堆的 “接口规范”：

- 对 调用者（其他  .c  文件）：只需包含头文件，就能用堆的功能，不用关心底层实现。

- 对 实现者（写堆逻辑的  .c  文件）：要按头文件的函数声明，去实现具体功能（如  HPInit  怎么

初始化、 HPPush  怎么扩容+调整 ）。

简单说，头文件像 “说明书”，定义了堆能用哪些功能、怎么用；实际的逻辑（函数体）写在对应的

 .c  文件里，实现 “接口和实现分离”，让代码更清晰、易维护。

1.2 实现文件(Heap.c)

1. 堆初始化函数---HPInit函数

void HPInit(HP* php) 
{php->arr = NULL;php->size = php->capacity = 0;
}

功能：把堆的结构体成员置为初始状态。

步骤：

1.  php->arr = NULL ：让存储堆数据的动态数组指针指向空，表明还没分配内存。

2.  php->size = 0 ：标记堆里当前没有有效元素。

3.  php->capacity = 0 ：标记数组容量为 0（还没分配空间 ）。

复杂度：

- 时间复杂度： O(1)  。直接赋值操作，和堆规模无关。

- 空间复杂度： O(1)  。没额外分配大内存，只是改几个变量值。

联系：是堆使用的“第一步”，后续 HPPush 等操作前，得先初始化堆结构体，让指针、容

量、大小有合法状态。

2. 堆的销毁函数---HPDestroy函数

void HPDestroy(HP* php) 
{if (php->arr) { free(php->arr); php->arr = NULL; }php->size = php->capacity = 0;
}

功能：释放堆占用的动态内存，防止内存泄漏，把堆恢复到“初始空状态”。

步骤：

1. 检查  php->arr  是否非空（非空才需要释放 ）。

2. 用  free(php->arr)  释放动态数组内存，再把  php->arr  置  NULL ，避免野指针。

3. 把  size  和  capacity  置为 0，让堆结构体回到初始化类似状态。

复杂度：

- 时间复杂度： O(1)  。就几个判断和赋值，释放内存是常数时间）。

- 空间复杂度： O(1)  。主要是释放已有内存，没新增大内存占用。

联系：堆不用了就调用它，和 HPInit 呼应，一个负责“开”，一个负责“关”，保证内存合理管

理。

3. 堆打印函数---HPPrint函数

void HPPrint(HP* php) 
{for (int i = 0; i < php->size; i++) {printf("%d ", php->arr[i]);}printf("\n");
}

功能：按数组顺序打印堆里的元素，方便调试看堆当前存了啥数据。

步骤：

用 for 循环遍历  php->arr  的前  php->size  个元素，逐个用  printf  输出，最后换行。

复杂度：

- 时间复杂度： O(n)  。 n  是堆当前元素个数（ php->size  ），循环次数和元素数量成正

比。

- 空间复杂度： O(1)  。没额外分配大内存，只是临时循环变量。

联系：纯调试辅助函数，和堆核心逻辑（增删调整）没直接关联，但调试时，调用

 HPPush / HPPop  后，用它打印能直观看堆数据变化。

4. 交换函数(辅助功能)---Swap函数

void Swap(int* x, int* y) 
{int tmp = *x;*x = *y;*y = tmp;
}

功能：交换两个 int 变量的值，堆调整（ AdjustUp / AdjustDown ）时，父子节点值需要交

换就靠它。

步骤：

用临时变量  tmp  存  *x  的值，把  *y  赋给  *x ，再把  tmp （原来的  *x  ）赋给  *y  。

复杂度：

- 时间复杂度： O(1)  。固定三步赋值，和变量值无关。

- 空间复杂度： O(1)  。就一个临时变量  tmp  。

联系：是  AdjustUp  和  AdjustDown  的“工具人”，堆调整时发现父子节点值不符合堆序

（大堆/小堆），用它交换值，让堆序恢复。

5. 堆向上调整函数---AdjustUp函数(核心)

在堆的插入函数和删除函数(后面会讲到)中，我们分别会用到堆向上调整函数和向下调整函数。所

以为了更好的维持代码的观赏性以及逻辑合理性。小编专门将堆向上和向下调整的逻辑封装成函

数。小编会用图片及文字的形式详细为大家讲解:

在堆的插入函数中:

将新数据插入到数组的尾上，再进行向上调整算法，直到满足堆。

向上调整算法:

- 先将元素插入到堆的末尾，即最后一个孩子之后

- 插入之后如果堆的性质(满足大堆或者小堆的顺序)遭到破坏，将新插入结点顺着其双亲往上调整

到合适位置即可

下面来看一个简单的例子:

这是堆插入元素时 向上调整（AdjustUp） 的完整过程演示，以“往大堆（父节点值 ≥ 子节点

值）中插入 10 ”为例，一步步看新元素如何“上浮归位”：

初始状态（插入前）

假设堆原本是一个大堆，结构如下（仅示意关键节点）：

- 根是  15 ，第二层  18 、 19 ，第三层  25 、 28 、 34 、 65  …… 所有父节点值 ≥ 子节点

值，满足大堆性质(即大堆)。

第一步：插入新元素到末尾

把新数据  10  放到堆的数组末尾（对应完全二叉树的“最后一个叶子节点”位置 ）。此时堆结

构被破坏（ 10  比父节点  28  小，不满足大堆“父 ≥ 子” ），需要调整。

第二步：第一次向上调整（和父节点  28  比较）

- 新元素  10  的下标是  child ，计算父节点下标  parent = (child-1)/2  → 找到  28 。

- 比较  10  和  28 ： 10 < 28 （大堆要求父 ≥ 子，这里子 < 父，不满足 ）→ 交换两者位置。

- 交换后， 10  跑到  28  的位置， 28  下沉到叶子。此时  10  的父节点变成  18 （继续检查

）。

第三步：第二次向上调整（和父节点  18  比较）

- 新的  child  是  18  的下标，重新算  parent = (child-1)/2  → 找到根节点  15 ？不，这里要

看交换后的层级：

实际步骤是：交换后  10  到了原  28  的位置，它的新父节点是  18 （第二层 ）。

- 比较  10  和  18 ： 10 < 18 （仍不满足大堆“父 ≥ 子” ）→ 再次交换两者位置。

- 交换后， 10  跑到  18  的位置， 18  下沉到下一层。此时  10  的父节点变成  15 （根节点

）。

第四步：第三次向上调整（和父节点  15  比较）

- 新的 child 是 15 的下标，算 parent = (child-1)/2  → 父节点不存在（已到根 ）。

- 比较 10  和 15 ： 10 < 15 （满足大堆“父 ≥ 子” ）→ 停止调整。
 
最终， 10  稳定在当前位置，堆重新满足大堆性质，插入完成。

核心逻辑总结:

向上调整的本质是：新元素从“末尾叶子”开始，不断和父节点比较，若不满足堆性质（大堆/

小堆）就交换，直到“父 ≥ 子（大堆）”或“父 ≤ 子（小堆）”，让新元素“浮”到正确层级。

这一系列交换，保证了插入后堆的结构仍然合法，是堆支持“动态插入”的关键！

下面我们来看代码的实现(先看向上调整函数的实现):

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 = (parent - 1) / 2;}else{break;}}
}

功能：让新插入的元素（在 child 位置 ）“往上爬”，直到满足堆的性质（大堆：子 <= 父；

小堆改符号即可 ）。

步骤：

1. 计算  child  对应的父节点下标  parent = (child - 1) / 2  。

2. 循环判断：只要  child > 0 （没到根节点 ），就比较  arr[child]  和  arr[parent]  。

- 若子 > 父（大堆情况 ），用 Swap 函数交换两者值，然后更新  child  为  parent ，再重新

算新的  parent  ，继续往上比较。

- 若子 <= 父，说明已满足堆序， 就break 跳出循环。

复杂度：

- 时间复杂度： O(log n)  。 n  是堆元素总数，每次调整最多从叶子走到根，路径长度是堆

的高度。

- 空间复杂度： O(1)  。就几个临时变量（ parent / child  ），和堆规模无关。

联系： HPPush  的核心！ HPPush  把新元素放数组末尾后，调用  AdjustUp  让它“归

位”，保证插入后堆还是合法的。

需要注意的是上面的这些内容都是使用向上调整函数调整为大堆的逻辑，如果要使用向上调整函数

调整为小堆的呢？要怎样实现？其实很简单:  如果要将堆从大堆改为小堆，核心是修改比较逻辑的

符号，但需要关注两个关键位置：

原大堆的比较条件是  arr[child] > arr[parent] （子 > 父 → 交换 ），小堆需要反过来：

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 = (parent - 1) / 2;}else{break;}}
}

修改点：

- 把  a[child] > a[parent]  改为  a[child] < a[parent]  。

- 含义：当子节点值 小于 父节点时，违反小堆“父 ≤ 子”的规则，需要交换，让更小的值往上

“浮”。

6. 堆插入函数---HPPush函数

void HPPush(HP* php, HPDataType x)
{assert(php); if (php->size == php->capacity) { int newCapcity = php->capacity == 0 ? 4 : 2 * php->capacity; HPDataType* tmp = (HPDataType*)realloc(php->arr, newCapcity * sizeof(HPDataType)); if (tmp == NULL){ perror("realloc fail!");exit(1); }php->arr = tmp; php->capacity = newCapcity; }php->arr[php->size] = x; AdjustUp(php->arr, php->size); ++php->size; 
}

功能：往堆里加新元素，同时保证堆的结构（大堆/小堆）不变。先处理扩容，再插入、调

整。

步骤：

1. 断言  php  非空（防止传空指针崩掉 ）。

2. 检查容量：若  size == capacity ，说明数组满了，需要扩容。

- 扩容策略：原来容量是 0 就开 4 个空间，否则开  2 * capacity  个空间。

- 用  realloc  重新分配内存，失败的话打印错误并退出。

3. 把新元素  x  放到数组末尾（ php->arr[php->size]  位置 ）。

4. 调用  AdjustUp ，让新元素从末尾开始向上调整，恢复堆序。

5.  size++ ，更新堆的元素个数。

复杂度：

- 时间复杂度： O(log n)  。主要耗时在  AdjustUp （ O(log n)  ），扩容的  realloc  是

 O(n) （复制原数据 ），但扩容是“均摊”的，整体可视为  O(log n)  。

- 空间复杂度： O(1) （不考虑扩容的话 ）。但扩容可能新增内存，不过也是为了存数据，通

常分析时，若元素总数是  n ，空间复杂度算  O(n) ；但函数本身临时变量是  O(1)  。

联系：是堆“新增元素”的入口，依赖  HPInit （初始化好结构体 ）、 AdjustUp （调整堆序

），也会触发  HPDestroy  要释放的动态内存扩容。

7. 判空函数---HPEmpty函数

bool HPEmpty(HP* php) 
{assert(php);return php->size == 0;
}

功能：判断堆里有没有元素，返回  true （空）或  false （非空 ）。

步骤：

断言  php  非空，然后返回  php->size == 0  的结果。

复杂度：

- 时间复杂度： O(1)  。直接判断  size  是否为 0 。

- 空间复杂度： O(1)  。

联系：在后面介绍的 HPPop 、 HPTop  等函数调用前，常用它判断堆是否为空，避免操作

空堆出错。比如HPPop  里  assert(!HPEmpty(php))  ，依赖它保证合法性。

8. 向下调整函数---AdjustDown函数(核心)

在上面我们详细介绍了向上调整函数，应用于插入数据函数中，现在我们讲解向下调整函数，不同

于之前，这个函数是应用于堆的删除中的。

在 堆的删除 函数中:

删除堆是删除堆顶的数据，将堆顶的数据跟最后一个数据一换，然后删除数组最后一个数据，再进

行向下调整算法。

向下调整算法有一个前提：左右子树必须是一个堆，才能调整。

向下调整算法:

- 将堆顶元素与堆中最后一个元素进行交换

- 删除堆中最后一个元素

- 将堆顶元素向下调整到满足堆特性为止

下面我们举个例子进一步体会删除数据和向下调整的过程:

 
假设堆是 小堆，用数组存储为： [10, 15, 19, 25, 18, 34, 65, 49, 27, 28]（对应图中树结构，

堆顶是  10 ，满足小堆“父 ≤ 子” ）。

堆删除步骤（小堆版）:  堆删除的目标是删除堆顶元素（ 10  ），流程分三步：

第一步：交换堆顶和最后一个元素

- 操作：将堆顶（ 10 ，下标  0  ）与最后一个元素（ 28 ，下标  9  ）交换。

- 结果：

- 数组变为： [28, 15, 19, 25, 18, 34, 65, 49, 27, 10] 

- 树结构（对应图中“第一步”）：堆顶变为  28 ，原堆顶  10  被挪到数组末尾。

第二步：逻辑删除最后一个元素

- 操作：堆的有效元素个数  size  减 1（假设原  size=10 ，现在  size=9  ）。

- 结果：

- 数组有效范围变为前  9  个元素： [28, 15, 19, 25, 18, 34, 65, 49, 27] 

- 原堆顶  10  被“逻辑删除”（后续操作不再访问 ）。

第三步：向下调整新堆顶（ 28  ），恢复小堆结构

交换后，新堆顶（ 28  ）可能不满足小堆“父 ≤ 子”的性质，需要向下调整，让其“下沉”到正确位

置。交换后，数组有效部分是  [28, 15, 19, 25, 18, 34, 65, 49, 27] （ size=9  ），新堆顶是

 28 （下标  0  ）。

第四步:  第一次向下调整（对应第二张图中的第一步）：

-  parent=0 （值  28  ），左孩子  child=1 （值  15  ），右孩子  child=2 （值  19  ）。

- 选子节点：小堆选更小的 →  15 < 19  → 选左孩子（ child=1  ）。

- 父子比较： 28 > 15 （父 > 子，违反小堆“父 ≤ 子” ）→ 交换

- 交换后数组： [15, 28, 19, 25, 18, 34, 65, 49, 27] 

- 更新  parent=1 （原  child  位置 ），新  child=parent * 2+1=1 * 2+1 = 3 （值  25  ）。

第五步:  第二次向下调整（对应第二张图中的第二步）：

-  parent=1 （值  28  ），左孩子  child=3 （值  25  ），右孩子  child=4 （值  18  ）。

- 选子节点：小堆选更小的 →  18 < 25  → 选右孩子（ child=4  ）。

- 父子比较： 28 > 18 （父 > 子，违反小堆 ）→ 交换

- 交换后数组： [15, 18, 19, 25, 28, 34, 65, 49, 27] 

- 更新  parent=4 （原 child 位置 ）,  新 child=parent * 2+1=4*2+1=9 （超过  size=9  ，循

环结束 ）。

最终结果（小堆恢复）：

调整后，数组为  [15, 18, 19, 25, 28, 34, 65, 49, 27] ，满足小堆“父节点 ≤ 子节点” 的性质：

-  15 ≤ 18 、 15 ≤ 19 

-  18 ≤ 25 、 18 ≤ 28 

- 所有父节点均小于等于子节点，堆结构恢复。

核心逻辑总结（小堆删除 + 向下调整）

1. 交换堆顶和末尾：用  O(1)  操作避免直接删堆顶的高成本，把堆顶移到数组末尾。

2. 逻辑删除末尾：用  size--  标记原堆顶为无效，不影响数组结构。

3. 向下调整新堆顶：利用小堆“选更小的子节点、父大则交换”的逻辑，让新堆顶（原末尾元

素 ）下沉到正确位置，恢复“父 ≤ 子”的小堆性质。

讲完了上面的例子，下面我们来看向下调整函数代码的实现

void AdjustDown(HPDataType* arr, int parent, int n) 
{int child = parent * 2 + 1; while (child < n) { if (child + 1 < n && arr[child] > arr[child + 1]) { child++; }if (arr[child] < arr[parent]) { Swap(&arr[child], &arr[parent]); parent = child;             child = parent * 2 + 1;     } else {break; }}
}

功能：让  parent  位置的元素“往下沉”，直到满足堆序（对应上述图片例子中的小堆为例

）。常用于删除堆顶、构建堆场景。

步骤：

1. 先选左孩子  child = parent * 2 + 1  。

2. 循环判断  child < n （在有效范围 ）：

- 若右孩子存在（ child + 1 < n  ）且右孩子值更小，选右孩子（ child++  ）。

- 比较  child  和  parent  的值：若子 < 父，交换两者，更新  parent  为  child ，重新算新

的  child  ，继续往下调整。

- 若子 <= 父，满足堆序， 就会 break跳出  。

复杂度：

- 时间复杂度： O(log n)  。从父节点往下调整，最多走到叶子，路径长度是堆高度

（ ~log₂n  ）。

- 空间复杂度： O(1)  。就几个临时变量（ child / parent  ）。

联系： HPPop  的核心！删除堆顶时，把最后一个元素放堆顶，然后调用  AdjustDown  让

它“下沉”，恢复堆结构。

上述代码是关于向下调整小堆的过程，那么要是向下调整大堆呢？

要把适配小堆的向下调整函数改为适配大堆，核心是调整选子节点的逻辑和父子交换的条

件，以下是具体步骤和对比：

小堆 → 大堆：核心逻辑差异:

堆类型 选子节点目标 选子节点条件（对比左右子节点） 父子交换条件（触发调整） 

小堆: 父节点尽可能小 选更小的子节点（ 左 > 右 → 选右 ） 子节点 < 父节点时交换 

大堆: 父节点尽可能大 选更大的子节点（ 左 < 右 → 选右 ） 子节点 > 父节点时交换 

改为大堆，需要修改两处核心逻辑：

1. 选子节点：找“更大的子节点”

把小堆的“选更小的子节点”条件，改为“选更大的子节点”：

// 大堆：选更大的子节点 → 条件改为 arr[child] < arr[child + 1]
if (child + 1 < n && arr[child] < arr[child + 1]) {  child++;  
}

- 逻辑：如果右子节点比左子节点大（ arr[child] < arr[child + 1]  ），就选右子节点（让父

节点和更大的子节点比较，保证父节点尽可能大 ）。

2. 父子交换条件：子节点 > 父节点时交换

把小堆的“子节点 < 父节点时交换”，改为“子节点 > 父节点时交换”： 

// 大堆：子节点 > 父节点时交换 → 条件改为 arr[child] > arr[parent]
if (arr[child] > arr[parent]) {  Swap(&arr[child], &arr[parent]);  parent = child;  child = parent * 2 + 1;  
} else {break;  
}

- 逻辑：当子节点值大于父节点值时，违反大堆“父节点 ≥ 子节点”的规则，需要交换，让父节

点变大。

修改后，适配大堆的向下调整函数：

void AdjustDown(HPDataType* arr, int parent, int n) {int child = parent * 2 + 1;  // 左孩子下标while (child < n) {  // 1. 大堆：选更大的子节点if (child + 1 < n && arr[child] < arr[child + 1]) {  child++;  // 右孩子更大，选右孩子}// 2. 大堆：子节点 > 父节点时交换（保证父 ≥ 子）if (arr[child] > arr[parent]) {  Swap(&arr[child], &arr[parent]);  parent = child;  // 继续向下调整child = parent * 2 + 1;  } else {break;  // 父 ≥ 子，满足大堆性质，退出}}
}

9. 堆删除函数(删除堆顶)---HPPop函数

void HPPop(HP* php) {assert(!HPEmpty(php)); Swap(&php->arr[0], &php->arr[php->size - 1]); --php->size; AdjustDown(php->arr, 0, php->size); 
}

功能：删除堆顶元素（大堆里的最大值/ 小堆里的最小值），并调整堆结构，保证删除后还是

合法堆。

步骤：

1. 断言堆非空（ !HPEmpty(php)  ），空堆删元素会出错。

2. 交换堆顶（ arr[0]  ）和最后一个元素（ arr[size - 1]  ）。

3.  size-- ，把原来的堆顶元素“移出”有效范围。

4. 调用  AdjustDown ，从新的堆顶（ arr[0]  ）开始向下调整，恢复堆序。

复杂度：

- 时间复杂度： O(log n)  。主要耗时在  AdjustDown （ O(log n)  ）。

- 空间复杂度： O(1)  。

联系：依赖  HPEmpty （判空 ）、 Swap （交换 ）、 AdjustDown （调整 ），是堆“删除

最优先元素（堆顶）”的关键操作。 

10. 取堆顶函数---HPTop函数

HPDataType HPTop(HP* php) 
{assert(!HPEmpty(php)); return php->arr[0]; 
}

功能：获取堆顶元素（大堆里的最大值/小堆里的最小值 ），方便用户查看堆的“最优先数

据”。

步骤：

断言堆非空，然后返回  arr[0]  的值（堆顶元素 ）。

复杂度：

- 时间复杂度： O(1)  。直接访问数组第一个元素。

- 空间复杂度： O(1)  。

联系：是堆“查最优先元素”的接口，常和  HPPop  配合，比如取堆顶后删除，实现“获取并

删除”逻辑。

函数间整体联系:

1. 初始化与销毁： HPInit  初始化堆， HPDestroy  销毁堆，是堆生命周期的“开始”和“结束”。

2. 增删操作：

-  HPPush  依赖  AdjustUp  完成插入后调整；

-  HPPop  依赖  Swap  交换堆顶和末尾、 AdjustDown  完成删除后调整。

3. 辅助与工具：

-  Swap  给  AdjustUp / AdjustDown  提供交换能力；

-  HPEmpty  给  HPPop / HPTop  提供判空保护；

-  HPPrint  用于调试，查看堆数据。

这些函数相互配合，实现了 堆的完整功能：初始化 → 插入 → 调整 → 删除 → 销毁，覆盖了堆作

为“优先队列”的核心操作（快速存取最优先元素 ）。

简单说，它们围绕“动态数组模拟堆结构，靠调整函数（ AdjustUp / AdjustDown  ）维持堆序”这个

核心，分工完成初始化、增、删、查、销毁等任务，让堆能作为独立数据结构被使用 。

1.3 测试文件(test.c)

#include"Heap.h"
void test01()
{HP hp;HPInit(&hp);HPPush(&hp, 56);HPPush(&hp, 10);HPPush(&hp, 15);HPPush(&hp, 30);//HPPush(&hp, 70);//HPPush(&hp, 25);HPPrint(&hp);HPPop(&hp);HPPrint(&hp);HPPop(&hp);HPPrint(&hp);HPPop(&hp);HPPrint(&hp);HPPop(&hp);HPPrint(&hp);HPDestroy(&hp);
}void test02()
{HP hp;HPInit(&hp);HPPush(&hp, 56);HPPush(&hp, 10);HPPush(&hp, 15);HPPush(&hp, 30);HPPrint(&hp);while (!HPEmpty(&hp)){int top = HPTop(&hp);printf("%d ", top);HPPop(&hp);}HPDestroy(&hp);
}int main()
{test01();test02();return 0;
}

这份测试代码主要是验证堆的基本操作是否正确，核心流程可以简单总结为：

1. 测试内容

通过两个函数（ test01  和  test02 ）测试堆的 初始化、插入、删除堆顶、取堆顶、判空、销毁 等

功能。

2. 关键操作解析

-  test01 ：

- 先初始化堆，插入  56、10、15、30  四个数据（插入时会自动调整为大堆/小堆结构）。

- 每次调用  HPPop  删除堆顶元素后，用  HPPrint  打印堆的当前状态，直观查看删除后堆的变

化。

- 最后销毁堆释放资源。

-  test02 ：

- 同样插入四个数据，然后用循环（ while (!HPEmpty) ）持续取堆顶元素（ HPTop ）并打印，同

时删除堆顶（ HPPop ），直到堆空。

- 目的是验证“取顶+删除”的循环操作是否符合堆的特性（比如大堆会依次输出最大值，小堆依次输

出最小值）。

3. 核心逻辑

- 堆的插入（ HPPush ）会通过“向上调整”维持堆结构（大堆/小堆）。

- 堆的删除（ HPPop ）会通过“交换堆顶和末尾元素→删除末尾→向下调整”恢复堆结构。

- 测试代码通过打印和输出，验证这些操作是否正确执行。

简单说：这段代码就是用实际数据“跑一遍”堆的增删查流程，看结果是否符合预期（比如大堆每次

删最大，小堆每次删最小）。

下面小编版完整版的代码留给大家:

1.4 完整代码

1. 头文件---Heap.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>//堆的结构
typedef int HPDataType;
typedef struct Heap
{HPDataType* arr;int size;     //有效数据个数int capacity; //空间大小
}HP;//交换函数
void Swap(int* x, int* y);
//向上调整函数
void AdjustUp(HPDataType* arr, int child);
//向下调整函数
void AdjustDown(HPDataType* arr, int parent, int n);//初始化函数
void HPInit(HP* php);
//销毁函数
void HPDestroy(HP* php);
//打印函数
void HPPrint(HP* php);//插入函数
void HPPush(HP* php, HPDataType x);
//删除函数
void HPPop(HP* php);
//取堆顶数据
HPDataType HPTop(HP* php);// 判空函数
bool HPEmpty(HP* php);

2. 实现文件---Heap.c

#include"Heap.h"void HPInit(HP* php)
{php->arr = NULL;php->size = php->capacity = 0;
}
void HPDestroy(HP* php)
{if (php->arr)free(php->arr);php->arr = NULL;php->size = php->capacity = 0;
}
void HPPrint(HP* php)
{for (int i = 0; i < php->size; i++){printf("%d ", php->arr[i]);}printf("\n");
}
void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}
void AdjustUp(HPDataType* arr, int child)
{int parent = (child - 1) / 2;while (child > 0){//大堆：>//小堆：<if (arr[child] > arr[parent]){//调整Swap(&arr[child], &arr[parent]);child = parent;parent = (child - 1) / 2;}else {break;}}
}
void HPPush(HP* php, HPDataType x)
{assert(php);//判断空间是否足够if (php->size == php->capacity){int newCapcity = php->capacity == 0 ? 4 : 2 * php->capacity;HPDataType* tmp = (HPDataType*)realloc(php->arr, newCapcity*sizeof(HPDataType));if (tmp == NULL){perror("realloc fail!");exit(1);}php->arr = tmp;php->capacity = newCapcity;}php->arr[php->size] = x;//向上调整AdjustUp(php->arr, php->size);++php->size;
}
// 判空
bool HPEmpty(HP* php)
{assert(php);return php->size == 0;
}
//向下调整算法
void AdjustDown(HPDataType* arr, int parent, int n)
{int child = parent * 2 + 1;//左孩子while (child < n){//大堆：<//小堆：>if (child + 1 < n && arr[child] < arr[child + 1]){child++;}//大堆: >//小堆：<if (arr[child] > arr[parent]){//调整Swap(&arr[child], &arr[parent]);parent = child;child = parent * 2 + 1;}else {break;}}
}
void HPPop(HP* php)
{assert(!HPEmpty(php));// 0 php->size-1Swap(&php->arr[0], &php->arr[php->size - 1]);--php->size;//向下调整AdjustDown(php->arr, 0, php->size);
}//取堆顶数据
HPDataType HPTop(HP* php)
{assert(!HPEmpty(php));return php->arr[0];
}

3. 测试文件---test.c

#include"Heap.h"
void test01()
{HP hp;HPInit(&hp);HPPush(&hp, 56);HPPush(&hp, 10);HPPush(&hp, 15);HPPush(&hp, 30);//HPPush(&hp, 70);//HPPush(&hp, 25);HPPrint(&hp);HPPop(&hp);HPPrint(&hp);HPPop(&hp);HPPrint(&hp);HPPop(&hp);HPPrint(&hp);HPPop(&hp);HPPrint(&hp);HPDestroy(&hp);
}void test02()
{HP hp;HPInit(&hp);HPPush(&hp, 56);HPPush(&hp, 10);HPPush(&hp, 15);HPPush(&hp, 30);HPPrint(&hp);while (!HPEmpty(&hp)){int top = HPTop(&hp);printf("%d ", top);HPPop(&hp);}HPDestroy(&hp);
}int main()
{test01();test02();return 0;
}

以上便是关于整个堆的实现内容，总体来说还是挺有难度的。特别是向上调整函数和向下调整函数

在堆插入函数和堆删除函数中的作用，值得大家反复理解和思考。后面还有关于堆的一个重要板块

——堆排序，即利用数据结构堆的思想来进行数据排序。小编会在下一篇文章中为大家进行讲解。

好了，最后感谢大家的观看！如果在写的过程中发现小朋友问题，也欢迎在评论区中指出！感谢大

家的观看！