C算法
数据结构：树、二叉树、堆排序与 TOP-K 问题解析
本文系统讲解了树、二叉树、堆等数据结构的基础概念、性质及存储结构。重点阐述了堆的构建、向上/向下调整算法，以及基于堆实现的堆排序和 TOP-K 问题解决方案。内容涵盖理论推导、代码实现示例及复杂度分析，适合希望深入理解底层数据结构的开发者学习。
本文系统讲解了树、二叉树、堆等数据结构的基础概念、性质及存储结构。重点阐述了堆的构建、向上/向下调整算法，以及基于堆实现的堆排序和 TOP-K 问题解决方案。内容涵盖理论推导、代码实现示例及复杂度分析，适合希望深入理解底层数据结构的开发者学习。
为什么我们要学那么多的数据结构？这是因为没有一种数据结构能够去应对所有场景。我们在不同的场景需要选择不同的数据结构，所以数据结构没有好坏之分，而评估数据结构的好坏要针对场景。
树是一种非线性的数据结构，它是由 n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
有一个特殊的结点，称为根结点，根结点没有前驱结点。除根结点外，其余结点被分成 M(M>0) 个互不相交的集合 T1、T2、……、Tm，其中每一个集合 Ti(1<= i <= m) 又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有 0 个或多个后继。因此，树是递归定义的。
结论：
树结构相对线性表比较复杂，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。这里主要了解最常用的孩子兄弟表示法。
typedef int DataType;
struct Node {
struct Node* child; // 左边开始的第一个孩子节点
struct Node* brother; // 指向其右边的下一个兄弟节点
DataType data; // 结点中的数据域
};
文件系统是计算机存储和管理文件的一种方式，它利用树形结构来组织和管理文件和文件夹。在文件系统中，树结构被广泛应用，它通过父节点和子节点之间的关系来表示不同层级的文件和文件夹之间的关联。
在树形结构中，我们最常用的就是二叉树，一棵二叉树是节点的一个有限集合，该节点是由一个根节点加上两棵别称为左子树和右子树的二叉树组成或者为空。
从上图可以看出二叉树具备以下特点：
根据二叉树的特点可知:
二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。
1. 顺序结构： 就是使用数组存储，一般使用数组只适合完全二叉树，因为不是完全二叉树会有空间的浪费，而在现实中使用中只有堆才会使用数组存储，需要注意的是这个里的堆和操作系统虚拟进程空间中的堆是两码事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。
2. 链式结构： 二叉树的链式存储结构是指用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。链式结构又分为二叉链和三叉链，当前我们学习中一般都是二叉链，后面学到高阶数据结构如红黑树等会用到三叉链。
堆是一种特殊的二叉树，具有二叉树的特性的同时，还具备其他特性。
定义：如果有一个关键码的集合 K = { k0, k1, ... kn-1 }，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：ki <= k2i+1 且 ki <= k2i+2 (ki >= k2i+1 且 ki >= k2i+2) i = 0,1,2...,则称为小堆 (或大堆)。将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆（在左右子树中根节点也是对应的最小 / 最大）
小根堆：堆顶是堆中最小的节点，大根堆：堆顶是堆中最大的节点
这里堆的定义和顺序表的定义是类似的。
typedef int HPDataType;
// 堆的结构
typedef struct Heap {
HPDataType* arr;
int size; // 有效数据个数
int capacity; // 容量
} HP;
和顺序表类似。
void HPInit(HP* php) {
assert(php);
php->arr = NULL;
php->capacity = php->size = 0;
}
void HPDestroy(HP* php) {
assert(php);
if (php->arr) free(php->arr);
php->arr = NULL;
php->capacity = php->size = 0;
}
是为了下一个插入数据方法做出铺垫，将插入的数据默认为孩子节点，根据二叉树的性质可知 parent=(child-1)/2，如果我们要实现的是小堆，那么：
// 交换
void Swap(int* x, int* y) {
int tmp = *x;
*x = *y;
*y = tmp;
}
// 向上调整算法 前提；往有效的堆中调整
void AdjustUp(HPDataType *arr, int child) {
int parent = (child - 1) / 2;
while (child > 0) {
// >: 大堆
// <: 小堆
if (arr[child] < arr[parent]) {
Swap(&arr[child], &arr[parent]);
child = parent;
parent = (child - 1) / 2;
} else {
break;
}
}
}
// 插入数据
void HPPush(HP* php, HPDataType x) {
assert(php);
if (php->size == php->capacity) {
int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
// 空间满了，需要增容
HPDataType* tmp = (HPDataType*)realloc(php->arr, sizeof(HPDataType) * newcapacity);
if (tmp == NULL) {
perror("realloc fail!\n");
exit(1);
}
php->arr = tmp;
php->capacity = newcapacity;
}
php->arr[php->size] = x;
// 向上调整
AdjustUp(php->arr, php->size);
++php->size;
}
这里和顺序表一样。
bool HPEmpty(HP* php) {
assert(php);
return php->size == 0;
}
返回堆中有效的数据个数。
int HPSize(HP* php) {
assert(php);
return php->size;
}
我们已知父亲节点来找孩子节点，假设我们要实现的是小堆，那么就需要让父亲节点和孩子节点比较，这里需要注意，我们需要让左右节点均要和父亲节点比，谁小谁和 parent 交换，然后让 parent 走到 child 位置，循环进行该操作直至 child 走到 n 结束。
void AdjustDown(HPDataType* arr, int parent, int n) {
int child = parent * 2 + 1;
while (child < n) {
// 先找最大的孩子，这里排序是<
// 如果是文件的是创建大堆，所以是>
if (child + 1 < n && arr[child] > arr[child + 1]) {
child++;
}
// 先找最大的孩子，这里排序是>
// 如果是文件的是创建大堆，所以是<
if (arr[child] < arr[parent]) {
Swap(&arr[child], &arr[parent]);
parent = child;
child = parent * 2 + 1;
} else {
break;
}
}
}
如果直接删除堆顶元素，让孩子节点均往前移动会导致原来的孩子节点变成父亲节点，左右孩子顺序不对等情况，如下图中原本 25 是 15 的左孩子，现在变成 56 的兄弟节点，那么我们就需要重新一个个调整，代价太大了，那么有没有方法可以解决？
我们交换堆顶元素和最后一个数据，然后让 size--，走到 a[5] 位置，a[5] 可以存储数据，但是不是有效的（即 10 不是堆中有序的数据），我们发现 70 变成了堆顶，但是 15 56 25 等数据之间的关系并没有发生变化，因此我们只需要让堆顶 70 向下调整，直接调用向下调整方法即可。
具体步骤如下：
判空后直接返回 a[0] 位置的数据即可。
HPDataType HPTOP(HP* php) {
assert(!HPEmpty(php));
return php->arr[0];
}
注意：上述所说的向上调整算法和向下调整算法均有个前提是往有效的堆中调整。
这里我们需要思考：排升序和排降序时需要建大堆还是小堆。这里第一反应是通过循环取堆顶元素发现排升序是建立小堆，降序建立大堆。那么是对还是错？？？
具体操作：
注意：大家这里可能疑惑为什么不直接打印堆顶元素，而是将堆顶元素取出来放入数组中，首先我们明确需要的条件是将数组排序，打印堆顶元素并没有直接改变数组中原本的数据。
// 排升序----建大堆，因为调用 AdjustDown 函数，将大的放到最后一个子节点，依次这样进行，会使得最小的在根节点处，就变成升序
// 排降序----建小堆，因为调用 AdjustDown 函数，将小的放到最后一个子节点，依次这样进行，会使得最大的在根节点处，就变成降序
// 借助数据结构---堆
void test01() {
int arr[] = {17, 20, 10, 13, 19, 15};
int n = sizeof(arr) / sizeof(arr[0]);
HP hp;
HPInit(&hp);
// 调用 push 将数组中的数据建堆
for (int i = 0; i < n; i++) {
HPPush(&hp, arr[i]);
}
int i = 0;
while (!HPEmpty(&hp)) {
arr[i++] = HPTOP(&hp);
HPPop(&hp);
}
for (int j = 0; j < n; j++) {
printf("%d ", arr[j]);
}
HPDestroy(&hp);
}
我们这里来看下我们之前学习过的冒泡排序的代码是如何的，经过比较发现冒泡排序是通过思想来实现排序，而上述的堆排序是通过使用数据结构——堆来辅助实现的，因此要实现堆排序需要借助堆的排序思想。
// 冒泡排序，时间复杂度 O（n^2）
void BubbleSort(int* arr, int n) {
for (int i = 0; i < n; i++) {
int exchange = 0;
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
exchange = 1;
Swap(&arr[j], &arr[j + 1]);
}
}
if (exchange == 0) {
break;
}
}
}
这里我们根据数组中存储的最后一个数据的有效下标（孩子节点）根据 parent=（child-1)/2 可得，依次递减 parent 直至根节点，结束循环。
大家可能疑惑在向下调整算法中可不可以从 a[0] 位置开始调整？答案是不可以，因为向上调整算法和向下调整算法成立的前提是该堆已经是有效的堆，从 a[0] 开始调整就相当于从有效的大/小堆中来调整大/小堆，所以不行，我们应该依次调整左右子树的大/小堆最后整体形成大/小堆。
注意：大家可能会把堆排序中的向上寻找 parent 节点认为是向上调整算法，但是如何确定是向上/向下调整算法的实质是调整方向，父亲节点——>子节点是向下调整，是通过比较两个孩子之间谁和父亲节点大/小来实现，可以保证堆的已有顺序不会被修改。
代码如下：
void HeapSort(int* arr, int n) {
// 根据给定的 arr 来进行建堆
// child:n-1 parent;(n-1-1)/2
for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
AdjustDown(arr, i, n);
}
}
时间复杂度： 我们发现如果要建的堆是满二叉树则一共有 2^h-1 个节点，最坏情况下就是从根节点到最后一个节点一次次往下移动（一层层移动），则 h=log2(n+1),向下调整为 logn，那么总时间复杂度为 nlogn。
那么可以使用向下调整算法建堆也是可以使用向上调整算法的，那么哪个时间复杂度更优捏？初次思考我们发现两个算法均是 nlogn，那么是不是如此呢？
向下调整算法证明： 因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明 (时间复杂度本来看的就是近似值，多几个结点不影响最终结果)： 需要移动节点总的移动步数为：每层节点个数 x 向上调整次数。
从第一层到最后一层节点个数逐渐增多，向下调整次数逐渐减少
向上调整算法时间复杂度证明： 这里和向下调整算法证明类似，最后可以得出 F(n)=(n+1)(log2(n+1)-2)+2，则时间复杂度为O(n*logn)。
结论：因此向下调整算法是堆排序中主流用法！
假设我们需要排降序，
结论：根据上述步骤我们得到: 排升序----建大堆，因为不断交换堆顶数据和最后一个位置数据交换，将大的放到最后一个子节点，依次这样进行，会使得最小的在根节点处，就变成升序 排降序----建小堆，因为不断交换堆顶数据和最后一个位置数据交换，将小的放到最后一个子节点，依次这样进行，会使得最大的在根节点处，就变成降序
TOP-K 问题：即求数据集合中前 k 个最大的元素或者最小的元素，一般情况下数据量都比较大。 比如：专业前 10 名，世界 500 强，富豪榜，游戏中前 100 的活跃玩家等。 对于 TOP-K 问题，能想到的最简单直接的方法就是排序，但是：如果数据量非常大，排序就不太可取了（可能数据都不能一下子全部加载到内存中），最佳的方法就是使用堆来解决，基本思路如下：
1. 用数据集合中前 k 个元素来建堆 前 k 个最大的元素，则建小堆 前 k 个最小的元素，则建大堆
2. 用剩余的 N-k 个元素依次与堆顶元素进行比较，不满足则替换堆顶元素 将剩余 N-K 个元素依次与堆顶元素比较完之后，堆中剩余的 k 个元素就是所求的前 k 个最小或者最大的元素
例子：假设·我们有 N 个数据，N 是 10 亿个整数，需要申请多大的内存？
换算： int = 4 byte 1G=1024MB=10241024KB=10241024*1024 byte
根据上述换算可得：1G 约等于 10 亿个字节，因此存储 10 亿数据需要申请 4G 内存。
如果面试官问我们，如果我们只有 1G 内存——我们该如何解决？ 这里我们可以分多次来存储，建立 4 个堆，每份都求取该堆中最大的几个数据，最后四个堆中数据个数相加为 k 即可。
那么假设只有 1KB 内存该如何呢？ 先取前 k 个数据进行建堆，遍历剩下的 N-K 个数据跟堆顶数据进行比较。
找最大的前 K 个数据，建小堆，因为堆顶是该堆中最小的数据，当我们每遍历一个数据就和堆顶比谁大，谁大谁入堆（小就出堆）。
创造数据：
void CreateNDate() {
// 造数据
int n = 100000;
srand(time(0));
const char* file = "data.txt";
FILE* fin = fopen(file, "w");
if (fin == NULL) {
perror("fopen error");
return;
}
for (int i = 0; i < n; ++i) {
int x = (rand() + i) % 1000000;
fprintf(fin, "%d\n", x);
}
fclose(fin);
}
生成了 data.txt 文件，里面存放了十万个整型数据。
遍历剩余的 N-K 个数据，和堆顶比大小，符合条件则调用向下调整算法。
void TopK() {
int k = 0;
printf("请输入 K：");
scanf("%d", &k);
// 读取文件中前 k 个数据建堆
const char* file = "data.txt";
FILE* fout = fopen(file, "r");
if (fout == NULL) {
perror("fopen error");
exit(1);
}
// 找最大的前 K 个数，建小堆
int* minHeap = (int*)malloc(sizeof(int) * k);
if (minHeap == NULL) {
perror("malloc fail!");
exit(2);
}
// 读取文件中前 K 个数据建堆
for (int i = 0; i < k; i++) {
fscanf(fout, "%d", &minHeap[i]);
}
// 建堆
for (int i = (k - 1 - 1) / 2; i >= 0; i--) {
AdjustDown(minHeap, i, k);
}
// 遍历剩下的 n-k 个数据，跟堆顶比较，谁大谁入堆
// 调整堆
int x = 0;
while (fscanf(fout, "%d", &x) != EOF) {
if (x > minHeap[0]) {
minHeap[0] = x;
AdjustDown(minHeap, 0, k);
}
}
for (int i = 0; i < k; i++) {
printf("%d ", minHeap[i]);
}
fclose(fout);
}
打印结果：
结论：找最大的前 K 个数据，建小堆，找最小的前 K 个数据，建大堆
本文以'长幼有序'为核心思想，系统解析了树形结构及其衍生数据结构的层次化特性与应用：
全文贯穿'层次决定顺序，结构决定效率'的理念，展示了数据结构从理论到实践的完整链路
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 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