C算法
数据结构堆详解：核心特性、实现与应用
本文深入解析数据结构中的堆。堆是一种满足特定规则的完全二叉树，通常用数组存储。分为大根堆和小根堆，支持 O(1) 获取最值，O(logN) 插入删除。文章涵盖堆的定义、结构、初始化、销毁、插入（向上调整）、删除（向下调整）等核心实现细节。同时介绍了建堆方法（向下/向上调整）、堆排序及 Top-K 问题解决方案，并包含相关选择题解析，帮助理解堆在高效处理最值问题中的应用。
本文深入解析数据结构中的堆。堆是一种满足特定规则的完全二叉树，通常用数组存储。分为大根堆和小根堆，支持 O(1) 获取最值，O(logN) 插入删除。文章涵盖堆的定义、结构、初始化、销毁、插入（向上调整）、删除（向下调整）等核心实现细节。同时介绍了建堆方法（向下/向上调整）、堆排序及 Top-K 问题解决方案，并包含相关选择题解析，帮助理解堆在高效处理最值问题中的应用。
堆的本质是满足特定规则的完全二叉树，同时通过数组存储以最大化空间利用率（用连续数组存储完全二叉树，无需额外存储指针，几乎没有内存浪费）。
逻辑结构：必为完全二叉树，不存在'断层'节点，所有叶子节点集中在最后两层，且最后一层节点靠左排列；
存储结构：物理上是连续数组，通过索引映射父子关系（设节点索引为 i）：
父节点索引：(i - 1) / 2（向下取整）；左子节点索引：2 * i + 1；右子节点索引：2 * i + 2；
最值特性：堆顶（数组第一个元素）始终是集合中的最大值（大根堆）或最小值（小根堆）。
小根堆：逻辑上根节点最小，数组存储为 [10, 15, 25, 56, 30, 70]；
大根堆：逻辑上根节点最大，数组存储为 [70, 56, 30, 15, 25, 10]。
堆的底层是用数组实现的，因此它的结构和顺序表的结构基本一致，具体定义如下：
typedef int HpDataType;
typedef struct Heap {
HpDataType* a;
int size;
int capacity;
} heap;
// 初始化堆
void HeapInit(heap* php) {
assert(php);
php->a = (HpDataType*)malloc(sizeof(HpDataType) * 4);
if (php->a == NULL) {
perror("malloc");
return;
}
php->capacity = 4;
php->size = 0;
}
// 堆的销毁
void HeapDestroy(heap* php) {
assert(php);
free(php->a);
php->a = NULL;
php->capacity = php->size = 0;
}
入堆的操作逻辑很简单：先把新数据直接插入到堆的末尾（对应数组的最后一个位置），插入后如果堆的结构不符合小根堆/大根堆的规则，就通过向上调整算法，把这个新元素逐步'往上挪'，直到它处于一个能让整个堆重新满足规则的位置。
// 入堆
void HeapPush(heap* php, HpDataType x) {
assert(php);
// 扩容
if (php->capacity == php->size) {
HpDataType* tmp = (HpDataType*)realloc(php->a, sizeof(HpDataType) * php->capacity * 2);
if (tmp == NULL) {
perror("realloc");
return;
}
php->a = tmp;
php->capacity = 2 * php->capacity;
}
php->a[php->size] = x;
php->size++;
// 向上调整
AdjustUp(php->a, php->size - 1);
}
【向上调整算法】：
// 交换算法
void swap(HpDataType* p1, HpDataType* p2) {
HpDataType x = *p1;
*p1 = *p2;
*p2 = x;
}
// 向上调整
void AdjustUp(HpDataType* a, int child) {
// 计算父节点的索引
int parent = (child - 1) / 2;
// 循环条件：child > 0 表示当前节点还没到堆顶（堆顶节点的 child 为 0，无父节点）
// 只要没到堆顶，就持续检查当前节点与父节点是否符合堆的规则
while (child > 0) {
// 孩子小于父亲就交换值
if (a[child] < a[parent]) {
swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
} else {
break;
}
}
}
这段向上调整算法是针对小根堆设计的；如果要适配大根堆，只需要把判断条件改成'子节点值大于父节点'即可。
堆的删除操作是针对堆顶元素的，具体逻辑是：先把堆顶元素和堆的最后一个元素交换位置，接着删除数组末尾（原堆顶元素），最后对新的堆顶元素执行向下调整算法，让堆重新满足规则。
之所以不直接删除堆顶元素，是因为堆顶是堆的核心节点，直接删除会彻底打乱整个堆的父子节点逻辑，后续几乎无法恢复成合法的堆结构。
// 出堆
void HeapPop(heap* php) {
assert(php);
assert(!HeapEmpty(php));
// 删除数据
swap(&php->a[0], &php->a[php->size - 1]);
php->size--;
// 向下调整
AdjustDown(php->a, php->size, 0);
}
【向下调整算法】:
// 交换算法
void swap(HpDataType* p1, HpDataType* p2) {
HpDataType x = *p1;
*p1 = *p2;
*p2 = x;
}
// 向下调整
void AdjustDown(HpDataType* a, int n, int parent) {
int child = 2 * parent + 1; // 假设左孩子小
while (child < n) {
// 选出孩子中小的那一个
if (child + 1 < n && a[child + 1] < a[child]) { // 避免越界访问
++child; // 假如右孩子小，child++
}
if (a[child] < a[parent]) {
swap(&a[child], &a[parent]);
parent = child;
child = 2 * parent + 1;
} else {
break;
}
}
}
这段代码实现的是小根堆的向下调整逻辑。如果要适配大根堆的出堆操作，只需要把两处判断条件的符号修改为'大于'即可：
子节点选择部分：将
a[child + 1] < a[child]改为a[child + 1] > a[child]（选出子节点中更大的那个）； 父子节点交换部分：将a[child] < a[parent]改为a[child] > a[parent]（若子节点值大于父节点，执行交换）。
（向下调整算法的时间复杂度逻辑一致：从堆顶向叶子节点移动，最大次数也是树的高度，复杂度同样为 O(logN)）
// 取堆顶元素
HpDataType HeapTop(heap* php) {
assert(php);
return php->a[0];
}
// 判空
bool HeapEmpty(heap* php) {
assert(php);
return php->size == 0;
}
// 堆元素个数
int HeapSize(heap* php) {
assert(php);
return php->size;
}
下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。根节点左右子树不是堆，我们怎么调整呢？
向下调整建堆逻辑：这里我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆；
建大根堆
// n: 数组中元素的总个数
// 核心逻辑：从最后一个非叶子节点开始，向前逐个调整节点，使每个子树满足堆的性质
// 最后一个非叶子节点的下标计算：
// 数组下标从 0 开始时，最后一个元素的下标是 n-1，它的父节点下标为 (n-1-1)/2
for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
// 对下标为 i 的节点进行"向下调整"，使以 i 为根的子树成为堆
AdjustDown(a, n, i);
}
向上调整法建堆：从第 2 个元素（i=1）开始，逐个对每个元素调用 AdjustUp，让新元素向上和父节点比较、交换，直到满足堆的性质，最终把整个数组建成堆；
// 建堆 -- 向上调整建堆
for (int i = 1; i < n; i++) {
AdjustUp(a, i);
}
这个过程其实相当于模拟堆的插入操作：每往堆里加入一个新元素，就对它做一次向上调整；等所有元素都插入并调整完毕，整个堆也就构建完成了。
向下调整建堆：O(N)
向上调整建堆：O(N * logN)
核心差异：
**堆排序（升序）思想：**先建大顶堆（堆顶是最大值），再反复将堆顶与堆尾交换（最大值归位），然后调整剩余元素为大顶堆，直到堆空，数组升序。
// 排升序 建大堆 O(N*logN)
void HeapSort_Up(int *a, int n) {
// 建堆 -- 向下调整建堆 -- O(N)
for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
AdjustDown(a, n, i);
}
int end = n - 1;
// 排序 -- O(N*logN)
while (end > 0) {
swap(&a[end], &a[0]);
AdjustDown(a, end, 0);
end--;
}
}
排降序的话，建小顶堆就行：堆顶始终是当前堆的最小值，把它和堆尾元素交换（最小值就放到了当前未排序区的末尾，逐步归位），再将剩下的元素重新调整为小顶堆，重复这个过程，直到堆处理完，数组就降序排好了。
// 排降序 建小堆 O(N*logN)
void HeapSort_Down(int* a, int n) {
// 建堆 -- 向上调整建堆 -- O(N*logN)
for (int i = 1; i < n; i++) {
AdjustUp(a, i);
}
int end = n - 1;
// 排序 -- O(N*logN)
while (end > 0) {
swap(&a[end], &a[0]);
AdjustDown(a, end, 0);
end--;
}
}
**TOP-K 问题：**即求数据集合中前 K 个最大的元素或者最小的元素，一般情况下数据量都比较大。比如：专业前 10 名、世界 500 强、富豪榜、游戏中前 100 的活跃玩家等。对于 Top-K 问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了 (可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：
- 用数据集合中前 K 个元素来建堆前 k 个最大的元素，则建小堆；前 k 个最小的元素，则建大堆
- 用剩余的 N-K 个元素依次与堆顶元素来比较，不满足则替换堆顶元素
// TOP-K 求前 k 个最大/最小的元素
// 前 k 个最大的元素，则建小堆
// 前 k 个最小的元素，则建大堆
// 当前 n = 15; k = 10;
// 求前 10 个最大的元素：
void TOP_K() {
// 造数据
int n = 15;
int* a = (int*)malloc(sizeof(int) * n);
srand((unsigned int)time(NULL));
for (size_t i = 0; i < n; ++i) {
a[i] = rand() % n + 1;
}
int k = 10;
// 向下调整建堆 -- 建小堆
for (int i = (k - 1 - 1) / 2; i >= 0; i--) {
AdjustDown(a, 10, i);
}
// 接下来剩下的元素和堆顶的元素进行比较
for (int i = k; i < n; i++) {
if (a[0] < a[i]) {
swap(&a[0], &a[i]);
// 向下调整
AdjustDown(a, 10, 0);
}
}
// 打印所有数据，观察是否满足
for (int i = 0; i < n; i++) {
printf("%d ", a[i]);
}
}
堆的判断需验证序列是否符合'大根堆（父节点≥子节点）'或'小根堆（父节点≤子节点）'的规则。以选项 A [100,60,70,50,32,65] 为例：
根节点 100，左子节点 60、右子节点 70（100≥60 且 100≥70，符合大根堆）；节点 60，左子节点 50、右子节点 32（60≥50 且 60≥32，符合）；节点 70，左子节点 65（70≥65，符合）；所有节点均满足大根堆规则，因此 A 是堆。
只有向下调整建堆的结果，所以选 C
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 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