树和二叉树的基础概念、性质及存储结构，重点讲解了堆（完全二叉树）的定义与大/小根堆特性。详细阐述了堆的向上调整与向下调整算法，并实现了堆的初始化、插入、删除、建堆等接口。最后通过堆排序展示了堆的应用，分析了其时间复杂度为 O(n log n)。内容涵盖数据结构核心知识点与 C 语言代码实现。
在计算机科学中，树是一种非常重要的非线性数据结构，它以层次化的方式组织数据，广泛应用于文件系统、编译原理、数据库索引等领域。而堆作为一种特殊的完全二叉树，不仅实现了高效的优先队列，更是堆排序算法的核心。本文将带你从树的基础概念出发，逐步深入堆的实现，并最终掌握堆排序的原理与代码编写。
树（Tree）是由 n（n≥0）个有限结点组成的一个具有层次关系的集合。当 n=0 时，称为空树。在任意一棵非空树中：
树的定义是递归的：树由根和若干互不相交的子树构成，而子树本身也是一棵树。
在实际编程中，我们需要用某种数据结构来存储树。树有多种表示方法，如双亲表示法、孩子表示法、孩子双亲表示法、孩子兄弟表示法等。最常用的是孩子兄弟表示法（也称为左孩子右兄弟表示法）。这种表示法可以将任意一棵树转化为二叉树的形式，从而方便地使用二叉树的算法进行处理。
孩子兄弟表示法的结点结构如下：
typedef int DataType;
struct Node {
struct Node* firstChild; // 指向第一个孩子结点
struct Node* pNextBrother; // 指向下一个兄弟结点
DataType data; // 结点中的数据域
};
树结构在计算机中应用广泛，最典型的例子就是文件系统的目录树结构。根目录类似于树的根结点，子目录和文件则对应分支结点和叶结点。通过树形结构，我们可以高效地组织和管理文件。
二叉树（Binary Tree）是每个结点最多有两个子树的树结构，并且子树有左右之分，次序不能颠倒。二叉树的定义也是递归的：
二叉树具有以下重要性质（假设根结点层数为 1）：
二叉树有两种常用的存储方式：顺序存储和链式存储。
顺序存储使用数组来存放二叉树的结点。对于完全二叉树，这种存储方式非常高效，因为结点在数组中的位置可以直接反映其逻辑关系（利用上述编号特性）。但对于非完全二叉树，数组会浪费大量空间，因此通常只用于完全二叉树（如堆）。
链式存储使用结点结构体，每个结点包含数据域以及指向左孩子和右孩子的指针。这是最常用的二叉树存储方式，结构如下：
typedef int BTDataType;
typedef struct BinaryTreeNode {
struct BinaryTreeNode* left; // 指向当前结点左孩子
struct BinaryTreeNode* right; // 指向当前结点右孩子
BTDataType data; // 当前结点值域
} BTNode;
如果有一个关键码的集合 K = {k₀, k₁, k₂, ..., kₙ₋₁}，将其所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：
堆具有以下性质：
堆通常使用顺序存储，即用一个一维数组来存储堆中的所有结点。由于堆是完全二叉树，数组下标可以自然映射结点位置：
下面我们以小堆为例，实现一个动态增长的堆。我们将提供以下接口：
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);
堆的核心操作是插入和删除，它们依赖于两个关键调整算法：向上调整和向下调整。
插入数据后如果堆的结构被破坏，那么就需要进行向上调整观察原堆的结构，如果插入之前是小堆，那么就将小的向上调整。如果插入之前是大堆，那么将向上调整的代码中的>改为<。我们这里都是小堆。
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;
}
}
}
删除堆顶元素时，通常先将堆顶与最后一个元素交换，然后删除最后一个元素（即原堆顶），再从新的堆顶开始向下调整：与左右孩子中较小（小堆）或较大（大堆）的交换，直到满足堆序或成为叶子。
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;
}
}
}
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;
}
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);
}
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);
}
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;
}
给定一个数组，我们如何将它调整成一个堆？常用的方法是向下调整建堆：从最后一个非叶子结点开始，依次向前对每个结点执行向下调整。最后一个非叶子结点的下标为 (n-1-1)/2 = n/2 - 1。
for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
AdjustDown(hp->_a, n, i);
}
堆排序是利用堆这种数据结构进行排序的一种算法，其基本思想是：
以升序排序为例，我们需要建大堆（这样堆顶是最大值），然后每次将最大值交换到最后，并调整剩余元素为大堆，最终得到升序序列。
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--;
}
}
注意：上述代码中的 AdjustDown 需要根据堆的类型调整比较逻辑。若用于大堆，向下调整时应将父结点与较大的孩子交换。
树作为重要的非线性结构，为我们提供了分层组织数据的能力。而堆作为完全二叉树的典型应用，不仅实现了优先队列，还衍生出高效的堆排序算法。通过本文的学习，我们掌握了堆的核心操作（向上调整、向下调整）及其在插入、删除、建堆、排序中的具体实现。希望读者能够动手编写代码，深入理解堆的精髓，并在实际问题中灵活运用。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 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