树的基本概念与堆的功能实现
处理层级数据时，树结构几乎是绕不开的选择。从文件系统到数据库索引，它的分层特性让组织信息变得井井有条。而堆作为完全二叉树的特例，则是实现高效优先队列的关键。
一、树的概念
1.1 树的定义
树（Tree）是由 n（n≥0）个有限结点组成的一个具有层次关系的集合。当 n=0 时，称为空树。在任意一棵非空树中：
- 有且仅有一个特定的结点称为根结点，根结点没有前驱结点。
- 除根结点外，其余结点可以分成 M（M>0）个互不相交的有限集合 T₁、T₂、...、Tₘ，其中每一个集合本身又是一棵树，称为根结点的子树。
树的定义是递归的：树由根和若干互不相交的子树构成，而子树本身也是一棵树。
1.2 树的相关术语
- 结点的度：一个结点拥有的子树个数。
- 叶结点（终端结点）：度为 0 的结点。
- 分支结点（非终端结点）：度不为 0 的结点。
- 父结点与子结点：若结点 A 有孩子 B，则 A 是 B 的父结点，B 是 A 的子结点。
- 兄弟结点：具有相同父结点的结点。
- 树的度：树中所有结点的度的最大值。
- 结点的层次：从根开始定义，根为第 1 层，根的子结点为第 2 层，以此类推。
- 树的高度（深度）：树中结点的最大层次。
- 森林：由 m（m≥0）棵互不相交的树组成的集合。
1.3 树的表示
在实际编程中，我们需要用某种数据结构来存储树。最常用的是孩子兄弟表示法（也称为左孩子右兄弟表示法）。这种表示法可以将任意一棵树转化为二叉树的形式，从而方便地使用二叉树的算法进行处理。
孩子兄弟表示法的结点结构如下：
typedef int DataType;
struct Node {
struct Node* firstChild; // 指向第一个孩子结点
struct Node* pNextBrother; // 指向下一个兄弟结点
DataType data; // 结点中的数据域
};
1.4 树在实际中的应用
树结构在计算机中应用广泛，最典型的例子就是文件系统的目录树结构。根目录类似于树的根结点，子目录和文件则对应分支结点和叶结点。通过树形结构，我们可以高效地组织和管理文件。
二、二叉树概念及结构
2.1 二叉树的定义
二叉树（Binary Tree）是每个结点最多有两个子树的树结构，并且子树有左右之分，次序不能颠倒。二叉树的定义也是递归的：
- 要么为空树；
- 要么由一个根结点加上两棵分别称为左子树和右子树的二叉树组成。
2.2 现实中的二叉树
现实生活中有很多二叉树的影子，比如家谱树、决策树等。
2.3 特殊的二叉树
-
满二叉树：如果一棵二叉树的每一层结点数都达到最大值，即深度为 k 的满二叉树有 2^k - 1 个结点，那么它就是满二叉树。满二叉树的特点是所有分支结点都有左右子树，且叶结点都在最底层。
-
完全二叉树：对于深度为 k 的二叉树，如果其结点与深度为 k 的满二叉树中编号从 1 至 n 的结点一一对应（即从上到下、从左到右编号），则称为完全二叉树。完全二叉树的特点是：
- 叶结点只可能出现在最后两层；
- 最后一层的叶结点都靠左排列；
- 若某个结点没有左孩子，则一定没有右孩子。
满二叉树是特殊的完全二叉树。
2.4 二叉树的性质
二叉树具有以下重要性质（假设根结点层数为 1）：
- 第 i 层最多结点数：在二叉树的第 i 层上，最多有 2^(i-1) 个结点（i ≥ 1）。
- 深度为 h 的最大结点数：深度为 h 的二叉树最多有 2^h - 1 个结点。
- 叶子结点数与度为 2 的结点数的关系：对任意非空二叉树，若叶子结点数为 n₀，度为 2 的结点数为 n₂，则 n₀ = n₂ + 1。这一性质可以通过总边数关系推导得出。
- 具有 n 个结点的完全二叉树深度：h = ⌊log₂(n)⌋ + 1（或 h = ⌈log₂(n+1)⌉）。
- 完全二叉树结点编号特性：若对完全二叉树按从上到下、从左到右从 0 开始编号，则对于编号为 i 的结点：
- 若 i > 0，其父结点编号为 (i-1)/2；
- 若 2i+1 < n，其左孩子编号为 2i+1，否则无左孩子；
- 若 2i+2 < n，其右孩子编号为 2i+2，否则无右孩子。
2.5 二叉树的存储结构
二叉树有两种常用的存储方式：顺序存储和链式存储。
1. 顺序存储
顺序存储使用数组来存放二叉树的结点。对于完全二叉树，这种存储方式非常高效，因为结点在数组中的位置可以直接反映其逻辑关系（利用上述编号特性）。但对于非完全二叉树，数组会浪费大量空间，因此通常只用于完全二叉树（如堆）。
2. 链式存储
链式存储使用结点结构体，每个结点包含数据域以及指向左孩子和右孩子的指针。这是最常用的二叉树存储方式，结构如下：
typedef int BTDataType;
typedef struct BinaryTreeNode {
struct BinaryTreeNode* left; // 指向当前结点左孩子
struct BinaryTreeNode* right; // 指向当前结点右孩子
BTDataType data; // 当前结点值域
} BTNode;
三、堆的概念与结构
3.1 堆的定义
如果有一个关键码的集合 K = {k₀, k₁, k₂, ..., kₙ₋₁}，将其所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：
- 大堆（大根堆）：任意结点的值都大于或等于其左右孩子结点的值，即 Kᵢ ≥ K₂ᵢ₊₁ 且 Kᵢ ≥ K₂ᵢ₊₂。
- 小堆（小根堆）：任意结点的值都小于或等于其左右孩子结点的值，即 Kᵢ ≤ K₂ᵢ₊₁ 且 Kᵢ ≤ K₂ᵢ₊₂。
堆具有以下性质：
- 堆中某个结点的值总是不大于或不小于其父结点的值。
- 堆总是一棵完全二叉树。
3.2 堆的存储结构
堆通常使用顺序存储，即用一个一维数组来存储堆中的所有结点。由于堆是完全二叉树，数组下标可以自然映射结点位置：
- 若根结点下标为 0，则对于下标为 i 的结点：
- 父结点下标：(i - 1) / 2
- 左孩子下标：2 * i + 1
- 右孩子下标：2 * i + 2
四、堆的基本功能实现
接下来我们动手写代码。以小堆为例，构建一个支持动态扩容的堆结构。核心接口设计如下：
typedef int HeapdataType;
typedef struct Heap {
HeapdataType* arr;
int size; // 这里的 size 指向最后一个元素的下一个位置，初始化时置为 0
int capacity; // 容量
} Hp;
void HeapInit(Hp* hp);
void HeapDestroy(Hp* hp);
void Swap(HeapdataType* n1, HeapdataType* n2);
void AdjustUp(HeapdataType* arr, int child);
void HeapPush(Hp* hp, HeapdataType x);
void AdjustDown(HeapdataType* arr, int size, int parent);
void HeapPop(Hp* hp);
HeapdataType HeapTop(Hp* hp);
int HeapSize(Hp* hp);
bool HeapEmpty(Hp* hp);
4.1 辅助函数：向上调整和向下调整
堆的核心操作是插入和删除，它们依赖于两个关键调整算法：向上调整和向下调整。
4.1.1 向上调整（AdjustUp）
插入数据后如果堆的结构被破坏，就需要进行向上调整。观察原堆的结构，如果插入之前是小堆，那么就将小的向上调整；如果插入之前是大堆，那么将向上调整的代码中的 > 改为 <。我们这里都是小堆。
void AdjustUp(HeapdataType* arr, int child) {
int parent = (child - 1) / 2;
while (child > 0) {
if (arr[parent] > arr[child]) {
Swap(&arr[parent], &arr[child]);
child = parent;
parent = (child - 1) / 2;
} else {
break;
}
}
}
4.1.2 向下调整（AdjustDown）
删除堆顶元素时，通常先将堆顶与最后一个元素交换，然后删除最后一个元素（即原堆顶），再从新的堆顶开始向下调整：与左右孩子中较小（小堆）或较大（大堆）的交换，直到满足堆序或成为叶子。
void AdjustDown(HeapdataType* arr, int size, int parent) {
// 因为我们要找出左右孩子中较小的那一个进行交换
// 我们先假设左孩子是较小的那一个
int child = 2 * parent + 1;
while (child < size) {
if (child + 1 < size && arr[child + 1] < arr[child]) {
child++;
}
if (arr[child] < arr[parent]) {
Swap(&arr[child], &arr[parent]);
parent = child;
child = 2 * parent + 1;
} else {
break;
}
}
}
4.2 接口实现
4.2.1 初始化与销毁
void HeapInit(Hp* hp) {
assert(hp);
hp->arr = NULL;
hp->capacity = hp->size = 0;
}
void HeapDestroy(Hp* hp) {
assert(hp);
free(hp->arr);
hp->arr = NULL;
hp->size = hp->capacity = 0;
}
4.2.2 插入元素
void HeapPush(Hp* hp, HeapdataType x) {
assert(hp);
if (hp->size == hp->capacity) { // 如果空间满了，对数组进行扩容
int newcapacity = hp->capacity == 0 ? 4 : 2 * hp->capacity;
HeapdataType* newarr = (HeapdataType*)realloc(hp->arr, sizeof(HeapdataType) * newcapacity);
if (newarr == NULL) {
perror("realloc failed");
return;
}
hp->arr = newarr;
hp->capacity = newcapacity;
}
hp->arr[hp->size++] = x;
AdjustUp(hp->arr, hp->size - 1);
}
4.2.3 删除堆顶元素
void HeapPop(Hp* hp) {
assert(hp);
assert(hp->size > 0); // 确保其中至少有一个元素
// 为了保证不同时改变左右子树的结构，我们将第一个元素与最后一个元素交换
Swap(&hp->arr[0], &hp->arr[hp->size - 1]);
hp->size--;
// 交换之后，我们需要将第一个元素进行向下调整，保证堆结构的完整性
AdjustDown(hp->arr, hp->size, 0);
}
4.2.4 其他简单接口
HeapdataType HeapTop(Hp* hp) {
assert(hp);
assert(hp->size > 0);
return hp->arr[0];
}
int HeapSize(Hp* hp) {
assert(hp);
return hp->size;
}
bool HeapEmpty(Hp* hp) {
assert(hp);
return hp->size == 0;
}
4.2.5 建堆
给定一个数组，我们如何将它调整成一个堆？常用的方法是向下调整建堆：从最后一个非叶子结点开始，依次向前对每个结点执行向下调整。最后一个非叶子结点的下标为 (n-1-1)/2 = n/2 - 1。
for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
AdjustDown(hp->_a, n, i);
}
五、堆排序
堆排序是利用堆这种数据结构进行排序的一种算法，其基本思想是：
- 建堆：将待排序序列构建成一个堆（升序建大堆，降序建小堆）。
- 排序：不断将堆顶元素与堆尾元素交换，交换后堆的大小减一，然后对新的堆顶执行向下调整，重复此过程直到堆为空。
以升序排序为例，我们需要建大堆（这样堆顶是最大值），然后每次将最大值交换到最后，并调整剩余元素为大堆，最终得到升序序列。
5.1 堆排序代码实现
void HeapSort(int* a, int n) {
// 1. 建堆（升序建大堆）
for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
AdjustDown(a, n, i);
}
// 2. 排序
int end = n - 1;
while (end > 0) {
Swap(&a[0], &a[end]); // 将堆顶（最大值）交换到最后
AdjustDown(a, end, 0); // 调整剩余的元素为大堆
end--;
}
}
这里有个细节要注意，向下调整的逻辑取决于你构建的是大堆还是小堆。若用于大堆，向下调整时应将父结点与较大的孩子交换。
5.2 堆排序的时间复杂度
- 建堆阶段：O(n)
- 排序阶段：每次交换后向下调整的时间复杂度为 O(log n)，共进行 n-1 次，因此排序阶段为 O(n log n)
- 总时间复杂度：O(n log n)
- 空间复杂度：O(1)（原地排序，不需要额外空间）
结语
树作为重要的非线性结构，为我们提供了分层组织数据的能力。而堆作为完全二叉树的典型应用，不仅实现了优先队列，还衍生出高效的堆排序算法。通过本文的学习，我们掌握了堆的核心操作（向上调整、向下调整）及其在插入、删除、建堆、排序中的具体实现。希望读者能够动手编写代码，深入理解堆的精髓，并在实际问题中灵活运用。
