C算法
堆（Heap）的实现：基于完全二叉树的顺序存储与调整算法
本文介绍了堆（Heap）的数据结构原理，基于数组实现完全二叉树映射。详细讲解了向上调整（插入）和向下调整（删除/建堆）的核心算法及代码实现，包含内存管理、常见易错点总结以及堆排序和 TopK 问题的应用拓展。重点分析了父子节点索引计算、边界条件处理及时间复杂度分析。
本文介绍了堆（Heap）的数据结构原理，基于数组实现完全二叉树映射。详细讲解了向上调整（插入）和向下调整（删除/建堆）的核心算法及代码实现，包含内存管理、常见易错点总结以及堆排序和 TopK 问题的应用拓展。重点分析了父子节点索引计算、边界条件处理及时间复杂度分析。
堆本质不是'树'，而是数组 + 完全二叉树的映射关系。
(i - 1) / 22 * i + 12 * i + 2数组：[10, 8, 7, 3, 2]
10
/ \
8 7
/ \
3 2
堆只做两件事：
| 操作 | 场景 | 本质 |
|---|---|---|
| 向上调整 | 插入 | 小往下，大往上 |
| 向下调整 | 删除 | 小往下沉，大往上顶 |
插入新元素。
新节点不断和父节点比较，如果更大则上浮。
void AdjustUp(int* 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;
}
}
}
parent 写在外面是'初始化 + 更新'结构，更清晰删除堆顶 / 堆排序。
每次选'更大的孩子'，和父节点比较。
void AdjustDown(int* 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;
}
}
}
| 情况 | 行为 |
|---|---|
| 只有左孩子 | 直接用 |
| 有左右孩子 | 选大的 |
| 没孩子 | 退出 |
顺序写反导致越界
a[child + 1] > a[child] && child + 1 < nchild + 1 < n && a[child + 1] > a[child]忘记 break
用右孩子做循环条件
while (child + 1 < n)void HPPush(HP* php, int x) {
if (php->size == php->capacity) {
int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
int* tmp = (int*)realloc(php->a, sizeof(int) * newcapacity);
if (tmp == NULL) {
perror("realloc fail");
exit(-1);
}
php->a = tmp;
php->capacity = newcapacity;
}
php->a[php->size] = x;
php->size++;
AdjustUp(php->a, php->size - 1);
}
void HPPop(HP* php) {
Swap(&php->a[0], &php->a[php->size - 1]);
php->size--;
AdjustDown(php->a, php->size, 0);
}
谁 malloc，谁 free。
free(php); ❌（如果是栈变量）void HPDestroy(HP* php) {
free(php->a);
php->a = NULL;
php->size = php->capacity = 0;
}
为什么 AdjustDown 要传 n？
n 用来限制'堆的有效范围'，防止访问已被移除的元素。为什么用左孩子做循环条件？
为什么不会越界？
child + 1 < n && ...，利用短路机制避免访问非法内存。三目运算符怎么用？
child = (child + 1 < n && a[child + 1] > a[child]) ? child + 1 : child;parent 为什么写在外面？
堆的调整不是'改整棵树'，而是修复一条路径。
for (int i = n - 1; i > 0; i--) {
Swap(&a[0], &a[i]);
AdjustDown(a, i, 0);
}
TopK 问题
优先级队列
建堆（Heapify）
for (int i = (n - 2) / 2; i >= 0; i--) {
AdjustDown(a, n, i);
}
(n-2)/2 开始？#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int HPDateType;
typedef struct Heap {
HPDateType* a;
int size;
int capacity;
} HP;
void Swap(HPDateType* p1, HPDateType* p2);
void AdjustUp(HPDateType* a, int child);
void AdjustDown(HPDateType* a, int n, int parent);
void HPInit(HP* php);
void HPDestroy(HP* php);
void HPPush(HP* php, HPDateType x);
void HPPop(HP* php);
HPDateType HPTop(HP* php);
bool HPEmpty(HP* php);
void CreatHeap(int* a, int n);
void HeapSort(int* a, int n);
#include "Heap.h"
void Swap(HPDateType* p1, HPDateType* p2) {
assert(p1 && p2);
HPDateType tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void AdjustUp(HPDateType* 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 AdjustDown(HPDateType* 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[parent] < a[child]) {
Swap(&a[parent], &a[child]);
parent = child;
child = parent * 2 + 1;
} else {
break;
}
}
}
void HPInit(HP* php) {
php->a = NULL;
php->capacity = php->size = 0;
}
void HPDestroy(HP* php) {
free(php->a);
php->a = NULL;
php->size = php->capacity = 0;
}
void HPPush(HP* php, HPDateType x) {
if (php->size == php->capacity) {
int newcapacity = php->capacity == 0 ? 4 : (php->capacity) * 2;
HPDateType* temp = (HPDateType*)realloc(php->a, sizeof(HPDateType) * newcapacity);
if (temp == NULL) {
perror("realloc fail");
exit(-1);
}
php->a = temp;
php->capacity = newcapacity;
}
php->a[php->size] = x;
php->size++;
AdjustUp(php->a, php->size - 1);
}
void HPPop(HP* php) {
assert(php);
assert(php->size != 0);
Swap(&(php->a[php->size - 1]), &php->a[0]);
php->size--;
AdjustDown(php->a, php->size, 0);
}
HPDateType HPTop(HP* php) {
assert(php);
assert(php->size != 0);
return php->a[0];
}
bool HPEmpty(HP* php) {
assert(php);
return php->size == 0;
}
void CreatHeap(int* a, int n) {
int i = (n - 2) / 2;
for (; i >= 0; i--) {
AdjustDown(a, n, i);
}
}
void HeapSort(int* a, int n) {
int i = (n - 2) / 2;
for (; i >= 0; i--) {
AdjustDown(a, n, i);
}
int end = n - 1;
while (end) {
int tmp = a[0];
a[0] = a[end];
a[end] = tmp;
AdjustDown(a, end, 0);
end--;
}
}
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online