堆（Heap）的实现：基于完全二叉树的顺序存储与调整算法（含完整代码）
目录
🧠 一、核心认知
堆本质不是“树”，而是：
数组 + 完全二叉树的映射关系
---
📌 完全二叉树的数组映射
父节点: (i - 1) / 2
左孩子: 2*i + 1
右孩子: 2*i + 2
---
🌲 结构示意图
数组: [10, 8, 7, 3, 2]
10
/ \
8 7
/ \
3 2
---
⚙️ 二、核心操作本质
堆只做两件事：
操作| 场景| 本质
向上调整| 插入| 小往下，大往上
向下调整| 删除| 小往下沉，大往上顶
---
🔼 三、向上调整（AdjustUp）
📌 使用场景
插入新元素
---
🧠 核心思想
新节点不断和父节点比较
如果更大 → 上浮
---
✅ 代码实现
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; } } }---
💡 关键点
- 只影响一条路径（O(log n)）
- parent 写在外面是“初始化 + 更新”结构，更清晰
---
🔽 四、向下调整（AdjustDown）
📌 使用场景
删除堆顶 / 堆排序
---
🧠 核心思想
每次选“更大的孩子”，和父节点比较
---
✅ 标准代码（推荐写法）
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; } } }---
🌟 设计巧妙点（重点）
1️⃣ 用左孩子控制循环（覆盖所有情况）
2️⃣ 用右孩子判断做分支（避免越界）
3️⃣ 把“左右比较”压缩成“选最优孩子”
---
📌 三种情况全覆盖
情况| 行为
只有左孩子| 直接用
有左右孩子| 选大的
没孩子| 退出
---
⚠️ 五、关键易错点总结
---
❌ 1. 顺序写反导致越界
a[child + 1] > a[child] && child + 1 < n ❌
✅ 正确：
child + 1 < n && a[child + 1] > a[child]
👉 利用短路避免越界
---
❌ 2. 忘记 break
👉 会死循环
---
❌ 3. 用右孩子做循环条件
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;
}
---
🧠 八、我的关键问题总结
---
❓1：为什么 AdjustDown 要传 n？
n 用来限制“堆的有效范围”
防止访问已被移除的元素
---
❓2：为什么用左孩子做循环条件？
因为：
有右孩子 ⇒ 一定有左孩子
👉 左孩子能覆盖所有情况
---
❓3：为什么不会越界？
因为：
child + 1 < n && ...
👉 利用短路机制避免访问非法内存
---
❓4：三目运算符怎么用？
child = (child + 1 < n && a[child + 1] > a[child]) ? child + 1 : child;
---
❓5：parent 为什么写在外面？
初始化 + 循环更新
结构更清晰
---
🧠 九、进阶理解（非常关键）
---
🎯 本质
堆的调整不是“改整棵树”
而是：
👉 修复一条路径
---
⏱ 时间复杂度
O(log n)
---
🚀 十、拓展 & 面试考点
---
⭐ 1. 堆排序（必考）
for (int i = n - 1; i > 0; i--)
{
Swap(&a[0], &a[i]);
AdjustDown(a, i, 0);
}
---
⭐ 2. TopK问题
👉 用小堆维护前K大元素
---
⭐ 3. 优先级队列
👉 堆的直接应用
---
⭐ 4. 建堆（Heapify）
for (int i = (n - 2) / 2; i >= 0; i--)
{
AdjustDown(a, n, i);
}
---
⭐ 面试高频问法
- 为什么从 "(n-2)/2" 开始？
- AdjustUp 和 AdjustDown 区别？
- 堆和二叉搜索树区别？
- 堆排序稳定吗？（❌ 不稳定）
---
📌 最终总结
堆 = 数组 + 完全二叉树映射
核心：
插入 → 向上调整
删除 → 向下调整
本质：
局部破坏 → 路径修复
---
🧠 个人反思
总结原理，注意细节传参是否正确
---
Heap.h
#pragma once #define _CRT_SECURE_NO_WARNINGS #pragma once #include<stdio.h> #include<assert.h> #include<stdlib.h> #include<stdbool.h> typedef HPDateType int; 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); Heap.c
#include"Heap.h" void Swap(HPDateType* p1, HPDateType* p2) { assert(p1 && p2); int a = *p1; *p1 = *p2; *p2 = a; } 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 k) //{ // int i = 1; // for (i; i < k; i++) // { // AdjustUp(a, i); // } //} void CreatHeap(int* a, int ) { // 1. 建堆 int i = (n-2)/2; for (i; i >= 0; i--) { AdjustDown(a, n, i); } } //堆排序 void HeapSort(int* a, int n) { // 1. 建堆 int i = (n - 2) / 2; for (i; i >= 0; i--) { AdjustDown(a, n, i); } // 2. 排序 int end = n - 1; while (end) { //Swap(&a[0], &a[end]); int tmp = a[0]; a[0] = a[end]; a[end] = tmp; AdjustDown(a, end, 0); end--; } }
