1. 堆的概念和定义
1.1 堆
堆本质上是一种特殊的完全二叉树。根据根节点的大小关系，通常分为大根堆和小根堆。
- 大根堆（大顶堆）：任意父节点的值都不小于其子节点的值，根节点最大。
- 小根堆（小顶堆）：任意父节点的值都不大于其子节点的值，根节点最小。
关键性质在于：堆中某个结点的值总是不大于或不小于其父结点的值，且堆总是一棵完全二叉树。这意味着我们可以用数组来紧凑地存储堆结构，无需额外的指针开销。
1.2 二叉树的性质
对于有 n 个结点的二叉树，如果从上到下、从左到右从 0 开始依次编号，对于编号为 i 的结点有以下下标计算规律：
- 父结点：
(i - 1) / 2 - 左孩子结点：
2 * i + 1 - 右孩子结点：
2 * i + 2
若 2 * i + 1 或 2 * i + 2 大于等于 n，则说明该结点没有对应的左右孩子。
2. 堆的实现
在 C 语言中，我们通常使用动态数组配合结构体来封装堆的操作接口。以下是堆的基本结构定义及常用函数声明。
typedef int HPDataType;
typedef struct Heap {
HPDataType* a; // 底层数组
int size; // 当前元素个数
int capacity; // 当前容量
} HP;
// 默认初始化堆
void HPInit(HP* php);
// 利用给定数组初始化堆
void HPInitArray(HP* php, HPDataType* a, int n);
// 堆的销毁
void HPDestroy(HP* php);
// 堆的插入
void HPPush(HP* php, HPDataType x);
// 获取堆顶数据
HPDataType HPTop(HP* php);
// 删除堆顶的数据
void HPPop(HP* php);
// 判空
bool HPEmpty(HP* php);
// 求 size
int HPSize(HP* php);
// 向上调整算法
void AdjustUp(HPDataType* a, int child);
// 向下调整算法
void AdjustDown(HPDataType* a, int n, int parent);
实际实现时，AdjustUp 用于插入新元素后维护堆序性，而 AdjustDown 常用于建堆或删除堆顶后的调整。注意边界条件，避免数组越界。
3. 实现链式二叉树
3.1 链式二叉树的概念
用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成：数据域和左右指针域。左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。
typedef int BTDataType;
// 二叉链
struct BinaryTreeNode {
struct BinaryTreeNode* left; // 指向当前结点左孩子
struct BinaryTreeNode* right; // 指向当前结点右孩子
BTDataType val; // 当前结点值域
};
3.2 前中后遍历
按照规则，二叉树的遍历主要有三种递归结构：
- 前序遍历（Preorder Traversal）：访问顺序为 根结点 -> 左子树 -> 右子树。
- 中序遍历（Inorder Traversal）：访问顺序为 左子树 -> 根结点 -> 右子树。
- 后序遍历（Postorder Traversal）：访问顺序为 左子树 -> 右子树 -> 根结点。
3.3 遍历示例
假设有一棵二叉树，根节点为 A，左子树包含 B、D，右子树包含 C、E、F。遍历时遇到空节点（NULL）表示该位置无子节点。具体输出如下：
- 前序遍历（根左右）：A, B, D, NULL, NULL, NULL, C, E, NULL, NULL, F, NULL, NULL
- 中序遍历（左根右）：NULL, D, NULL, NULL, B, A, NULL, E, NULL, C, NULL, F, NULL
- 后序遍历（左右根）：NULL, NULL, D, NULL, B, NULL, NULL, E, NULL, NULL, F, C, A
这里展示的是带空节点的完整序列，便于理解递归调用的路径。在实际应用中，通常只关注非空节点的访问顺序。