跳到主要内容数据结构初阶：堆的实现 | 极客日志C算法
数据结构初阶：堆的实现
堆是一种基于完全二叉树的顺序存储结构，支持高效的插入与删除操作。通过向上调整和向下调整算法维护堆性质，可实现大根堆或小根堆。文章提供完整的 C 语言代码示例，演示初始化、Push、Pop、Top 等功能，并应用于排序及 Top-K 问题求解。重点阐述堆的数组存储特性、时间复杂度分析及代码细节。
橘子海1 浏览 数据结构初阶：堆的实现
我们使用顺序结构实现完全二叉树，也就是堆的实现。堆除了存储数据，还有其他的价值——排序，是一个功能性的数据结构。
小根堆堆顶的数据一定是最小的，大根堆堆顶的数据一定是最大的。选出最大/最小，再选次大/次小……不断选最后就帮助排序。还可以解决取前几、后几的 TOP-K 问题。
我们以建大堆为例。建小堆只需改变 parent < child 即可。
一、初始化
下面多次用到交换，将交换分装成函数。
Heap.h
#include <stdbool.h>
typedef int HPDataType;
typedef struct Heap {
HPDataType* a;
int size;
int capacity;
} HP;
void HeapInit(HP* php);
void HeapDestroy(HP* php);
Heap.c
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int HPDataType;
typedef struct Heap {
HPDataType* a;
int size;
int capacity;
} HP;
void HeapInit(HP* php) {
assert(php);
php->a = (HPDataType*)malloc((HPDataType) * );
(php->a == ) {
perror();
;
}
php->size = ;
php->capacity = ;
}
{
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
sizeof
4
if
NULL
"malloc fail"
return
0
4
void
Swap
(HPDataType* p1, HPDataType* p2)
二、插入
堆的底层就是数组，可以插入数据。要把控制数组想象成控制树。原来是大根堆，插入后，要求还得是堆。插入前是堆，插入后会影响部分祖先（跟祖先调整）。
以大根堆为例，看最简单的情况：插入 20，插入后不影响堆的性质。
再插入 60，插入后要调整。为保证 父亲 > 娃，要交换。娃还 > 父亲，继续交换。父亲 > 娃，结束。
上面的过程叫 向上调整，最多调整高度次，时间复杂度：O(log N)。插入一个数据，想让他再调整成堆只要 log N 次。
堆的插入不像链表、顺序表，不能想往哪插就往哪插，要保持性质。上面的尾插，如果堆原来是这样，就不能尾插 20。所以插入单纯的叫 Push 就好，因为不是由接口指定在哪个位置插入。
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, sizeof(HPDataType) * php->capacity * 2);
if (tmp == NULL) {
perror("malloc fail");
return;
}
php->a = tmp;
php->capacity *= 2;
}
php->a[php->size] = x;
php->size++;
AdjustUp(php->a, php->size - 1);
}
三、删除（堆顶、根）
为什么删堆顶、根才有意义？老大被干掉了，老二才能冒头。
堆实现的意义，无论是排序还是 top-k，本质是在帮我选数，选出最大/最小数。
不能挪动删除（直接删）！原因：1.效率低下 2.父子兄弟关系全乱了。
正确方法：(间接删) 堆顶和最后的元素换一下；--size，使换下去的最后一个（原堆顶）元素失效。
1.效率高 2.最大程度的保持了父子关系。
单看左右子树依旧是大堆，换上去的原最后元素大概率是比较小的，就要 向下调整。
看下面的新场景：为保证换了之后父亲 > 娃，现在的堆顶（原最后一个元素）要跟大的娃换。娃中大的 > 爸，把爸换下去。继续换。
最坏情况调到叶子结束。物理上是数组，怎么判断到叶子——没有娃，怎么判断没有娃呢？把它当做爸，算左娃的下标，如果超出数组范围就没娃，所以参数要多给个数组的大小 size，用来判断 child 是否越界。
void AdjustDown(HPDataType* a, int n, int parent) {
int child = parent * 2 + 1;
while (child < n) {
if (child + 1 < n && a[child] < a[child + 1])
{
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);
}
防止右娃越界那里的 child + 1 万万不能写成 <= n！！！
下面整体代码中，排序那里，如果写成 <= n，会出问题。每打印完堆顶数据，后面的 HeapPop 里，会先交换堆顶，尾数据，再 size--；此时，堆尾数据还在，不过没有访问权限了；堆的大小也没变，再 HeapPush 会把原堆尾数据覆盖，作为新堆尾。如果写成 <= n，size-- 的作用就消失了，堆尾最大的数据访问权限又回来了。在 AdjustDown 的 Swap 中，堆尾的数据又换到堆内部了。
向上调整的前提：除了 child 这个位置，前面的数据构成堆。
向下调整的前提：保证左右子树都是堆。
四、完整代码
Heap.h
#include <stdbool.h>
typedef int HPDataType;
typedef struct Heap {
HPDataType* a;
int size;
int capacity;
} HP;
void HeapInit(HP* php);
void HeapDestroy(HP* php);
void HeapPush(HP* php, HPDataType x);
void HeapPop(HP* php);
HPDataType HeapTop(HP* php);
bool HeapEmpty(HP* php);
int HeapSize(HP* php);
void AdjustUp(HPDataType* a, int child);
void AdjustDown(HPDataType* a, int n, int parent);
Test.c
#include <stdio.h>
#include <stdlib.h>
#include "Heap.h"
void test1()
{
HP hp;
HeapInit(&hp);
HeapPush(&hp, 2);
HeapPush(&hp, 45);
HeapPush(&hp, 76);
HeapPush(&hp, 23);
HeapPush(&hp, 5654);
HeapPush(&hp, 24);
HeapPush(&hp, 5);
HeapPush(&hp, 242);
HeapPush(&hp, 25);
while (!HeapEmpty(&hp)) {
printf("%d ", HeapTop(&hp));
HeapPop(&hp);
}
HeapDestroy(&hp);
}
void test2()
{
HP hp;
HeapInit(&hp);
HeapPush(&hp, 2);
HeapPush(&hp, 45);
HeapPush(&hp, 76);
HeapPush(&hp, 23);
HeapPush(&hp, 5654);
HeapPush(&hp, 24);
HeapPush(&hp, 5);
HeapPush(&hp, 242);
HeapPush(&hp, 25);
HeapPush(&hp, 5);
HeapPush(&hp, 5);
int k = 0;
scanf("%d", &k);
while (!HeapEmpty(&hp) && k--) {
printf("%d ", HeapTop(&hp));
HeapPop(&hp);
}
HeapDestroy(&hp);
}
Heap.c
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "Heap.h"
typedef int HPDataType;
typedef struct Heap {
HPDataType* a;
int size;
int capacity;
} HP;
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 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, sizeof(HPDataType) * php->capacity * 2);
if (tmp == NULL) {
perror("malloc fail");
return;
}
php->a = tmp;
php->capacity *= 2;
}
php->a[php->size] = x;
php->size++;
AdjustUp(php->a, php->size - 1);
}
void AdjustDown(HPDataType* a, int n, int parent) {
int child = parent * 2 + 1;
while (child < n) {
if (child + 1 < n && a[child] < a[child + 1])
{
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 HeapDestroy(HP* php) {
assert(php);
free(php->a);
php->a = NULL;
php->size = php->capacity = 0;
}
