堆（Heap）的实现：基于完全二叉树的顺序存储与调整算法（含完整代码）

目录

🧠 一、核心认知

⚙️ 二、核心操作本质

🔼 三、向上调整（AdjustUp）

🔽 四、向下调整（AdjustDown）

🌟 设计巧妙点（重点）

📌 三种情况全覆盖

⚠️ 五、关键易错点总结

🚀 六、堆的核心接口实现

🧩 七、内存管理（非常重要）

🧠 八、我的关键问题总结

🧠 九、进阶理解（非常关键）

🚀 十、拓展 & 面试考点

🧠 一、核心认知

堆本质不是“树”，而是：

数组 + 完全二叉树的映射关系

---

📌 完全二叉树的数组映射

父节点: (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--; } }