二叉树与堆：从非线性结构到 O(N) 建堆

树是第一个必须用递归去理解的结构。放弃线性思维——这是进入二叉树的门票。

为什么需要树

前面几节课的顺序表、链表、栈、队列，都是线性结构：每个元素最多一个前驱、一个后继，数据排成一条线。

但现实不总是线性的。文件系统的目录、家谱、编译器的语法树、操作系统的进程树——它们都是一对多的关系，一条链装不下。

有 C 语言基础的人会立刻撞上第一个疑问：结构体里放一个指向自己的指针，怎么写？答案是 C 完全支持（struct Node* next;）。真正难的不是语法，而是两件事：

1. 如何用线性内存表达非线性关系；
2. 用递归而不是循环去处理它。

树是第一个必须用递归理解的数据结构。这不是风格问题，是结构决定的。

树的概念：一次把术语说清

树的定义是递归的：

• 有一个特殊的结点叫根结点（Root），它没有前驱；
• 除根结点外，其余结点被分成 M (M>0) 个互不相交的集合 T1、T2、……、Tm，其中每个集合本身又是一棵结构类似的子树。

"互不相交"是硬约束。两棵子树一旦共用结点，它就不是树。

树由"倒挂的树"得名：根朝上，叶朝下。

术语表

这张表是后面所有内容的地基，尤其"度"和"层次"两个概念。

术语	定义	备注
结点的度	该结点含有的子树（孩子）个数	图中 A 的度为 6
叶结点 / 终端结点	度为 0 的结点	B、C、H、I……
分支结点 / 非终端结点	度不为 0 的结点	D、E、F、G……
双亲结点 / 父结点	含子结点的那个结点	A 是 B 的父结点
孩子结点 / 子结点	结点所拥有子树的根	B 是 A 的孩子
兄弟结点	具有相同父结点的结点	B、C 是兄弟；F、G 不是
堂兄弟结点	双亲在同一层的结点	同层但不是亲兄弟的那些
树的度	树中最大的结点的度	取最大值，不是求和
结点的层次	从根开始定义，根为第 1 层	见下方说明
树的高度 / 深度	树中结点的最大层次	高度 = 最大层次
祖先	从根到该结点所经分支上的所有结点	A 是所有结点的祖先
子孙	以某结点为根的子树中任一结点	所有结点都是 A 的子孙
森林	m (m>0) 棵互不相交的树的集合	树去掉根就是森林

两个容易踩的点：

1. "兄弟"是亲兄弟。具有相同父结点的才算。F 和 G 看起来在同一层，但父结点不同，只能算堂兄弟——人类亲缘关系里怎么叫，这里就怎么叫。
2. 层次建议从第 1 层开始。教材允许从第 0 层起算，但为了让"空树高度为 0"这条逻辑自洽，建议统一采用根为第 1 层。这个约定要一路带到后面的堆下标推导里去。

树的表示：孩子兄弟表示法

树要存起来比线性表麻烦——既要保存值域，又要保存结点之间的关系。教材提到双亲表示法、孩子表示法、孩子双亲表示法等，其中**孩子兄弟表示法（Child-Sibling Representation）**最常用：

typedef int DataType;

struct Node
{
    struct Node* firstChild1;   // 第一个孩子结点
    struct Node* pNextBrother;  // 指向其下一个兄弟结点
    DataType data;              // 结点中的数据域
};

思路是"左孩子、右兄弟"：每个结点只记两个指针——第一个孩子，和它的下一个兄弟。任意多叉树都能塞进这个二叉结构里，这是后面学高阶树结构时的通用技巧。

现实中的树

最标准的例子是文件系统的目录树。

二叉树：有左右之分的树

概念

一棵二叉树是结点的一个有限集合，该集合：

1. 或者为空；
2. 或者由一个根结点加上两棵分别称为左子树和右子树的二叉树组成。

两条推论：

1. 二叉树不存在度大于 2 的结点；
2. 二叉树的子树有左右之分，次序不能颠倒——所以二叉树是有序树。

第 2 条经常被忽略。把左右子树对调，得到的是另一棵二叉树。

两种特殊形态

形态	定义	关系
满二叉树（Full Binary Tree）	每一层的结点数都达到最大值；层数为 K 时结点总数为 2^K − 1	是特殊的完全二叉树
完全二叉树（Complete Binary Tree）	深度为 K、有 n 个结点，当且仅当每个结点都与深度为 K 的满二叉树中编号从 1 至 n 的结点一一对应	效率很高，能直接用数组存

完全二叉树的关键特征是结点连续：按层序编号时中间不能有空洞。后面堆能用数组存、下标能直接算父子关系，全靠这一条。

同样层数，结点数能差一倍

"满"和"完全"的区别，在固定层数时看得最清楚。设层数为 h，两种极端形态是：

	形态	度为 0（n0）	度为 1（n1）	度为 2（n2）	结点总数 n
最多	每一层都满	2^(h−1)	0	2^(h−1) − 1	2^h − 1
最少	前 h−1 层满，第 h 层只有 1 个	2^(h−2)	1	2^(h−2) − 1	2^(h−1)

于是同一个 h 底下，结点总数可以相差一倍。反过来，从 n 求 h 有两条路：

满二叉树的深度：h = log₂(n + 1)
完全二叉树的最小深度：h = log₂n + 1

这两条不是两个公式，而是同一个事实的两端：n = 2^h − 1 时 h 取到下限，n = 2^(h−1) 时 h 取到上限。对任意完全二叉树，2^(h−1) ≤ n ≤ 2^h − 1，两边取对数就得到上面两式。这也是上一节第 4、5 道练习题的解题依据。

⚠️ 最少情形里 n1 = 1 是有原因的：第 h 层那个"独苗"是它父结点唯一的孩子，所以那个父结点的度是 1。树里一旦出现度为 1 的结点，结点总数就一定是偶数——n = n0 + n1 + n2 且 n0 = n2 + 1，代入得 n = 2·n2 + 1 + n1，只有 n1 = 1 时 n 才是偶数。这就是第 3 题"2n 个结点的完全二叉树"能解出来的原因。

✶ Insight ─────────────────────────────────────

• 上下界都靠 n0 = n2 + 1 做自检。上表两行分别代入：最多 2^(h−1) = 2^(h−1) − 1 + 1 ✓，最少 2^(h−2) = 2^(h−2) − 1 + 1 ✓。任何一个推导算完，先拿这条性质验一遍。
• n1 的取值只有 0 和 1 两种可能——这是完全二叉树"结点连续"这条约束的直接后果。一般二叉树没有这个限制。
  ─────────────────────────────────────────────────

二叉树的五条性质

1. 若规定根结点的层数为 1，则非空二叉树第 i 层上最多有 2^(i−1) 个结点。
2. 若规定根结点的层数为 1，则深度为 h 的二叉树最大结点数是 2^h − 1。
3. 对任何一棵二叉树，若度为 0 的叶结点个数为 n0，度为 2 的分支结点个数为 n2，则 n0 = n2 + 1。
4. 若规定根结点的层数为 1，具有 n 个结点的满二叉树的深度 h = log₂(n+1)。
5. 对于具有 n 个结点的完全二叉树，如果按从上至下、从左至右的顺序从 0 开始编号，则对序号为 i 的结点：
   • 若 i > 0，双亲序号为 (i−1)/2；i = 0 时为根结点，无双亲；
   • 若 2i+1 < n，左孩子序号为 2i+1，否则无左孩子；
   • 若 2i+2 < n，右孩子序号为 2i+2，否则无右孩子。

n0 = n2 + 1 的推导

这条性质用得最多，教材给了一个很干净的代数证明——从两个不同视角数同一样东西：

/*
 * 假设二叉树有 N 个结点
 * 从总结点数角度考虑：N = n0 + n1 + n2          ①
 *
 * 从边的角度考虑：N 个结点的任意二叉树，总共有 N-1 条边
 * 因为二叉树中每个结点都有双亲，根结点没有双亲，
 * 每个结点向上与其双亲之间存在一条边，
 * 因此 N 个结点的二叉树总共有 N-1 条边
 *
 * 度为 0 的结点没有孩子，故不产生边；
 * 度为 1 的结点只有一个孩子，产生一条边；
 * 度为 2 的结点有两个孩子，产生两条边；
 * 所以总边数为：n1 + 2*n2
 *
 * 故从边的角度考虑：N-1 = n1 + 2*n2          ②
 * 结合 ① 和 ② 得：n0 + n1 + n2 = n1 + 2*n2 - 1
 * 即：n0 = n2 + 1
 */

"结点总数"和"边的总数"是同一棵树的两种数法，联立消掉 n1，结论自然浮现。

五道练习题

1. 某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（ ）
   A 不存在这样的二叉树　B 200　C 198　D 199
2. 下列数据结构中，不适合采用顺序存储结构的是（ ）
   A 非完全二叉树　B 堆　C 队列　D 栈
3. 在具有 2n 个结点的完全二叉树中，叶子结点个数为（ ）
   A n　B n+1　C n−1　D n/2
4. 一棵完全二叉树的结点数为 531 个，那么这棵树的高度为（ ）
   A 11　B 10　C 8　D 12
5. 一个具有 767 个结点的完全二叉树，其叶子结点个数为（ ）
   A 383　B 384　C 385　D 386

解析：

• 第 1 题：直接套 n0 = n2 + 1 = 199 + 1 = 200。
• 第 2 题：只有完全二叉树用数组存不浪费空间；堆是特殊的完全二叉树，队列和栈本来就是线性结构。答案是非完全二叉树。
• 第 3 题：结点总数是偶数，说明有一个度为 1 的结点。2n = n0 + 1 + n2 且 n0 = n2 + 1，解得 n0 = n。
• 第 4 题：2⁹ − 1 = 511 < 531 ≤ 2¹⁰ − 1 = 1023，所以高度为 10。
• 第 5 题：767 是奇数，度为 1 的结点数为 0。767 = n0 + n2 且 n0 = n2 + 1，解得 n0 = 384。

答案：1.B　2.A　3.A　4.B　5.B

存储结构：顺序 vs 链式

二叉树有两种存储方式，先看对比：

维度	顺序存储（数组）	链式存储（链表）
适用对象	完全二叉树	任意二叉树
空间	非完全二叉树会大量浪费	每个结点多两个指针域
父子定位	下标公式直接算	靠指针跳转
典型代表	堆	搜索树、红黑树

顺序存储物理上是一个数组，逻辑上是一棵二叉树。现实中只有堆才会用数组存二叉树。

链式存储中每个结点由三个域组成：数据域 + 左右指针域。按指针数量分为两类：

typedef int BTDataType;

// 二叉链
struct BinaryTreeNode
{
    struct BinTreeNode* left;   // 指向当前结点左孩子
    struct BinTreeNode* right;  // 指向当前结点右孩子
    BTDataType data;            // 当前结点值域
};

// 三叉链
struct BinaryTreeNode
{
    struct BinTreeNode* parent; // 指向当前结点的双亲
    struct BinTreeNode* left;   // 指向当前结点左孩子
    struct BinTreeNode* right;  // 指向当前结点右孩子
    BTDataType data;            // 当前结点值域
};

现阶段用二叉链就够；红黑树这类高阶结构才会用到三叉链。

⚠️ 名字容易误导：“三叉链"指的是结点里有三个指针（父 + 左 + 右），不是"度为 3 的树”。 二叉树"每个结点最多两个孩子"这条约束不会因为用了三叉链就改变——多出来的那个指针指向上方（双亲），不是第三个孩子。代价是每个结点多一个指针的开销，换来的是找双亲从 O(N) 降到 O(1)（否则只能从根重新搜一遍）。

堆：完全二叉树的顺序存储

概念

如果有一个关键码的集合 K = {k0, k1, ……, kn−1}，把它的所有元素按完全二叉树的顺序存储方式存放在一个一维数组中，并满足：

• 任意父结点都 ≤ 其子结点 → 小堆（小根堆）；
• 任意父结点都 ≥ 其子结点 → 大堆（大根堆）。

则称这个集合为堆。根结点最大的堆叫最大堆，根结点最小的堆叫最小堆。

堆的两条性质：

1. 堆中某个结点的值总是不大于或不小于其父结点的值；
2. 堆总是一棵完全二叉树。

为什么必须是完全二叉树？因为只有完全二叉树按层序存进数组才没有空洞，下标才落得回 (i−1)/2、2i+1、2i+2 这套公式上。下标公式和完全二叉树是一体两面的东西——这也是为什么堆必须、且只能用顺序结构。

三个必须记住的约束

1. 堆只约束父子，不约束兄弟。左右孩子谁大谁小，堆不关心。所以堆不是有序序列。
2. 兄弟之间没有大小顺序，这一点在堆排序那一节会变成关键论据。
3. 数据结构里的"堆"和操作系统里的"堆区"是两回事。前者是逻辑结构，后者是物理内存区域的划分，名字相同，学科不同，没有直接关联。

四道练习题

1. 下列关键字序列为堆的是（ ）
   A 100,60,70,50,32,65　B 60,70,65,50,32,100　C 65,100,70,32,50,60
   D 70,65,100,32,50,60　E 32,50,100,70,65,60　F 50,100,70,65,60,32
2. 已知小根堆为 8,15,10,21,34,16,12，删除关键字 8 之后需重建堆，在此过程中，关键字之间的比较次数是（ ）
   A 1　B 2　C 3　D 4
3. 一组记录排序码为 (5 11 7 2 3 17)，则利用堆排序方法建立的初始堆为
   A (11 5 7 2 3 17)　B (11 5 7 2 17 3)　C (17 11 7 2 3 5)
   D (17 11 7 5 3 2)　E (17 7 11 3 5 2)　F (17 7 11 3 2 5)
4. 最小堆 [0,3,2,5,7,4,6,8]，在删除堆顶元素 0 之后，其结果是（ ）
   A [3,2,5,7,4,6,8]　B [2,3,5,7,4,6,8]　C [2,3,4,5,7,8,6]　D [2,3,4,5,6,7,8]

答案：1.A　2.C　3.C　4.C

第 4 题的完整过程值得手推一遍：堆顶 0 与末尾 8 交换 → [8,3,2,5,7,4,6] → 8 与较小的孩子 2 交换 → [2,3,8,5,7,4,6] → 8 再与较小的孩子 4 交换 → [2,3,4,5,7,8,6]。这就是下一节的向下调整。

向下调整算法

向下调整是堆的两个核心算法之一。它有一个前提：

左右子树必须已经是一个堆，才能调整。

也就是说，它不能把一个乱数组直接变成堆，只能"修复"根结点这一处的破坏。

以 int array[] = {27,15,19,18,28,34,65,49,25,37}; 为例（逻辑上是一棵完全二叉树，除根外左右子树都已是小堆），从根开始调整：

void AdjustDown(HPDataType* a, int n, int parent)  // 小堆向下调整
{
    // 可能左孩子小，可能右孩子小，先假设左孩子小
    int child = parent * 2 + 1;  // 右孩子的下标永远比左孩子大 1

    while (child < n)  // child >= n 说明孩子不存在，调整到叶子了
    {
        // 找出小的那个孩子
        if (child + 1 < n && a[child + 1] < a[child])
        {
            // 判断右孩子下标小于 n，防止越界；且右孩子小于左孩子，则向右移动
            ++child;
        }

        if (a[child] < a[parent])
        {
            Swap(&a[child], &a[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}

拆开看，三个要点：

• 假设法。先假设左孩子小，再检查右孩子是否存在且更小，是就 ++child。这样只用一份比较逻辑，不必为"左小/右小"写两个分支。这是全篇反复出现的技巧——之前合并两条有序链表时也用过类似的假设法。
• 结束条件用 child < n。物理上数组里没有"叶子"这个标记，判断叶子的方式就是"算出来的孩子下标越界了"。完全二叉树没有左孩子就不可能有右孩子，所以只判左孩子即可。
• child + 1 < n 不能省。右孩子可能根本不存在，少了这个判断就会读到数组外面去。

小堆向下调整的过程，本质是把小的往上调、大的往下沉。

堆的完整实现

堆底层是动态数组，所以初始化和扩容的套路与顺序表一致。

头文件

#pragma once

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

typedef int HPDataType;

typedef struct Heap
{
    HPDataType* a;
    int size;
    int capacity;
} HP;

void HPInit(HP* php);
void HPDestory(HP* php);
void HPPush(HP* php, HPDataType x);
void HPPop(HP* php);
HPDataType HPTop(HP* php);
bool HPEmpty(HP* php);

初始化与销毁

void HPInit(HP* php)
{
    assert(php);
    php->a = NULL;
    php->size = 0;
    php->capacity = 0;
}

void HPDestory(HP* php)
{
    assert(php);
    free(php->a);       // 释放的是动态数组，不是结构体本身
    php->a = NULL;
    php->size = 0;
    php->capacity = 0;
}

assert(php) 保护的是"传入的指针不为空"这个假定。函数入口处检查参数有效性，是一条硬规矩。

销毁时释放的必须是 php->a。HP 结构体往往是调用方栈上的局部变量，free(php) 释放的是一块不属于堆内存的地址。

向上调整算法

插入操作要用的就是这个。

新元素先放到数组末尾——逻辑上就是"最后一个叶子结点的右边"。放进去之后，堆的性质可能被破坏，因为它可能比父结点还小（小堆）。这时从新结点出发，沿着到根的路径往上比：

void AdjustUp(HPDataType* 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;
        }
    }
}

注意 int parent = (child - 1) / 2; 写在循环外：第一次进入循环体之前就得先算一次父结点，否则第一轮比较用的 parent 是未初始化的值。这是这段代码最容易漏的一行。

插入

void HPPush(HP* php, HPDataType x)
{
    assert(php);

    // ① 空间满了先扩容
    if (php->size == php->capacity)
    {
        int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
        HPDataType* tmp = (HPDataType*)realloc(php->a, newcapacity * sizeof(HPDataType));
        if (tmp == NULL)
        {
            perror("realloc failed");
            return;
        }
        php->a = tmp;
        php->capacity = newcapacity;
    }

    // ② 把新元素放到数组的尾部
    php->a[php->size] = x;
    php->size++;

    // ③ 对新元素进行向上调整
    AdjustUp(php->a, php->size - 1);
}

三步：判满扩容 → 尾插 → 向上调整。

realloc(php->a, ...) 在原有内存上扩容；capacity 为 0 时 php->a 是 NULL，realloc(NULL, size) 等价于 malloc(size)，一次调用覆盖两种情况。

⚠️ 这里必须是 realloc 或"malloc 新空间 + 拷贝旧数据"。如果写成 malloc 新空间后直接 php->a = tmp，之前存进去的元素会被整块丢掉。编译器不会拦你——这是本节"常见误区"里的一条。

删除堆顶

删除特指删除堆顶元素。为什么不能直接删？两个后果：

1. 把 a[0] 后面的元素整体前移，数组搬移成本 O(N)；
2. 父子关系全乱——原来的兄弟变成了父子，堆性质彻底失效。

正确做法是"首尾交换法"：

void HPPop(HP* php)
{
    assert(php);
    assert(php->size > 0);

    Swap(&php->a[0], &php->a[php->size - 1]);  // 堆顶与末尾交换
    php->size--;                               // 逻辑上删除末尾元素

    AdjustDown(php->a, php->size, 0);          // 再从根向下调整
}

交换之后，原来的末尾元素到了堆顶，它多半是小堆里最大的那个，于是从根执行一次向下调整就能把堆修好。因为只删末尾，不需要搬移任何元素。

这里也可以看出为什么 AdjustDown 要单独接收 n：php->size 在 size-- 之后已经是"当前有效元素个数"，正好当调整范围的上界用。

取堆顶与判空

HPDataType HPTop(HP* php)
{
    assert(php);
    assert(php->size > 0);

    return php->a[0];
}

bool HPEmpty(HP* php)
{
    assert(php);

    return php->size == 0;
}

HPTop 的返回类型必须是 HPDataType——取到值却不返回，调用方什么也拿不到。取堆顶是 O(1) 操作，这正是堆相对于其他结构的核心价值。

建堆：两种算法，差一个数量级

给一个无序数组，怎么把它变成堆？有两种做法。

方法一：向上调整建堆（模拟插入）

把数组第 0 个元素看成规模为 1 的堆，然后从下标 1 开始逐个"插入"，每次插入都对当前位置执行一次向上调整：

for (int i = 1; i < n; i++)
{
    AdjustUp(a, i);
}

逻辑上就是"把每个元素依次往前插入"。整个过程不需要额外开空间，也不用扩容。最坏情况下第 i 个元素要往上走 log i 层，累加起来是 O(N log N)。

方法二：向下调整建堆（倒着调）

向下调整要求左右子树都是堆。可刚拿到数组时谁都不是堆，怎么满足这个前提？

答案是从最后一个非叶子结点开始，倒着往前调：

for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
    AdjustDown(a, n, i);
}

道理是：

• 叶子结点自己就是合法的堆，不需要调整；
• 倒着走，调到某个结点时，它的左右子树已经被全部调成堆了——前提自动满足。

起始下标 (n - 1 - 1) / 2 就是最后一个结点的父结点：最后一个结点下标是 n-1，它的父结点是 ((n-1) - 1) / 2 = (n - 2) / 2。

这个写法把堆排序从"必须先写一个堆数据结构"里解放出来。它只需要 AdjustDown 这一个算法，堆就是数组本身。

复杂度对比

教材用满二叉树做的推导给出的结论是：

建堆方式	时间复杂度	特点
向上调整建堆	O(N log N)	好理解，模拟插入的过程
向下调整建堆	O(N)	效率更高，形式更简洁

为什么倒着调反而更快？直觉是：越靠下的结点越多，但它们需要下调的层数越少。满二叉树最后一层占了接近一半的结点，一步都不用走。把这些"零成本"的结点算进去，总和就收敛到 O(N)，而不是 O(N log N)。严格证明要用错位相减法。

📖 参考：《数据结构知识库》第四节 · 堆 —— “自底向上建堆是 O(n)（不是 O(n log n)）”；第七节常见误区也单列了这一条。

堆排序

堆排序（Heap Sort） 分两步：

1. 建堆：升序建大堆，降序建小堆；
2. 利用堆删除的思想排序。

为什么"升序建大堆、降序建小堆"

直觉上很多人会反过来，认为"要升序，那选出最小值，不是应该建小堆吗"。这个想法在选出第一个数之后就会撞墙。

以"排降序却建了大堆"为例：

• 堆顶是所有数里最大的，它该放在数组末尾（降序的最后一个位置）；
• 把它和末尾交换后，剩下的数里要选次大的；
• 但这时不参与排序的那部分从开头被破坏——剩下的数的父子关系已经错乱（原来的兄弟变成了父子），不再是堆了；
• 想选出次大值就得重新建堆，而重新建堆是 O(N)，整体退化到 O(N²)。

问题的根源是堆只能从根被"局部修复"。删除堆顶时交换的是末尾，末尾元素本来就在堆结构之外，所以剩下部分仍然是完整的堆，一次 O(log N) 的向下调整就能修好。而如果往开头方向操作，被破坏的前缀恰好是下一步还要用堆的那部分——关系全断，修不回来。

所以正确组合是：

目标	建堆	每轮把堆顶换到哪
升序	大堆	数组末尾
降序	小堆	数组末尾

统一规律：建什么堆，取决于你想把哪个极值放到末尾。

代码

void HeapSort(int* a, int n)
{
    // 降序，建小堆；升序，建大堆
    // 向下调整建堆：从最后一个非叶子结点倒着调
    for (int i = (n - 1 - 1) / 2; i >= 0; i--)
    {
        AdjustDown(a, n, i);
    }

    int end = n - 1;
    while (end > 0)
    {
        Swap(&a[0], &a[end]);   // 堆顶（极值）换到末尾
        AdjustDown(a, end, 0);  // 只对前 end 个元素向下调整
        --end;
    }
}

三个细节：

1. end 一开始是 n - 1，而它同时也等于"前面还参与排序的元素个数"——所以可以直接当 AdjustDown 的 n 用。这是这段代码最巧的地方。
2. 每轮 --end，有序区从后往前扩大，堆的范围从后往前缩小。
3. 循环条件是 end > 0：只剩一个元素时它必然已经在正确位置，不需要再处理。

整体复杂度 O(N log N)，且原地排序，额外空间 O(1)。

先用接口版跑一遍：TestHeap1

HeapSort 是原地算法，全程看不到 HPPush / HPPop，反而不好理解它和"删除堆顶"到底什么关系。所以先用堆的接口写一遍同样的逻辑，两者对照：

void TestHeap1()
{
    int a[] = { 4,2,8,1,5,6,9,7,3,2,23,55,232,66,222,33,7,1,66,3333,999 };
    HP hp;
    HPInit(&hp);
    for (size_t i = 0; i < sizeof(a)/sizeof(int); i++)
    {
        HPPush(&hp, a[i]);
    }

    int i = 0;
    while (!HPEmpty(&hp))
    {
        printf("%d ", HPTop(&hp));
        //a[i++] = HPTop(&hp);
        HPPop(&hp);
    }
    printf("\n");

输出是这 21 个数的降序排列（实测）：

3333 999 232 222 66 66 55 33 23 9 8 7 7 6 5 4 3 2 2 1 1

这就是堆排序：数据依次入堆（插入过程自动建成了大堆），再反复"取堆顶 → 删堆顶"。因为 HP 内部是大堆，HPTop 每次拿到的都是当前最大值，弹出的顺序自然有序。

那行被注释掉的 a[i++] = HPTop(&hp); 暗示了这个版本的代价：

	接口版（TestHeap1）	原地版（HeapSort）
空间	额外开一个堆，O(N)	复用原数组，O(1)
实现	调 HPPush / HPPop	直接写 AdjustDown
复杂度	O(N log N)	O(N log N)

复杂度一样，空间差一整个 N。HeapSort 把堆直接建在待排序数组上，省掉了这份复制——这也解释了为什么 HeapSort 里一个 HPPush 都见不到：堆的接口被拆开，只留下真正需要的那两步（建堆 + 向下调整）。如果取消那行注释，a[i++] = HPTop(&hp) 会把弹出结果写回原数组，效果与 HeapSort 相同，代价是多占一份 O(N) 的堆空间。

弹出 k 次：找前 k 大的接口版写法

TestHeap1 里还留了一段注释掉的代码：

// 找出最大的前k个
int k = 0;
scanf("%d", &k);
while (k--)
{
    printf("%d ", HPTop(&hp));
    HPPop(&hp);
}

弹出 k 次，每次弹出的都是当前最大值，结果是正确的。但它有个硬前提：所有数据都必须已经在堆里。为了找前 k 个，得先把 N 个全部装进内存——N 一大就崩了。这正是下一节 Top-K 要解决的问题。

堆排序的测试函数很短，顺带记一笔：

void TestHeap2()
{
    int a[] = { 4,2,8,1,5,6,9,7,2,7,9 };
    HeapSort(a, sizeof(a) / sizeof(int));
}

Top-K 问题

TOP-K 问题：即求数据集合中前 K 个最大的元素或者最小的元素，一般情况下数据量都比较大。

场景很具体：专业前 10 名、世界 500 强、富豪榜、游戏前 100 的活跃玩家。

为什么不能排序

最直接的想法是排完序取前 K 个。数据量不大时这没问题，但 Top-K 的典型场景恰好相反。

把 N 取到十亿量级，账立刻就算不平了：

量	小算盘
N = 10 亿，每个数 4 字节	10 亿 × 4 = 40 亿字节 = 4 GB
K = 1000，真正想要的只有前 1000 个	1000 × 4 = 4000 字节 = 4 KB

为了拿到 4 KB 的答案，得先准备 4 GB 的内存。 普通机器根本分配不出来——排序这条路不是"慢"，而是从第一步就走不通。

注意问题不在 O(N log N)：这个复杂度并不慢。问题在于它要求整个数据集同时在内存里。而堆的做法只要求 4 KB。

堆的做法

用一个大小为 K 的堆去筛选：

1. 用数据集合中前 K 个元素建堆：
   • 求前 K 个最大的元素 → 建小堆；
   • 求前 K 个最小的元素 → 建大堆；
2. 用剩余的 N−K 个元素依次与堆顶元素比较，满足条件则替换堆顶元素，然后向下调整。

以"求前 K 个最大"为例：堆里始终存着"目前为止见过的最大的 K 个数"，而堆顶是这 K 个里最小的那个——它就是这道门槛的守门人。新元素想进来，必须先打败守门人：

• 新元素 ≤ 堆顶 → 连这 K 个里最小的都打不过，直接丢弃；
• 新元素 > 堆顶 → 它比堆里那个更有资格，替换堆顶并向下调整。

比完 N−K 个元素，堆里剩下的 K 个就是答案。

复杂度上，建堆 O(K)，后面每个元素最多一次 O(log K) 的调整，整体 O(N log K)，空间只有 O(K)——不管 N 是一千万还是一亿，内存里始终只放 K 个元素。

代码

课件给了 PrintTopK 的骨架，函数体留白：

void PrintTopK(int* a, int n, int k);

实现之前，有个坑必须先绕开——它不是编译错误，是静默的错误结果。

一个坑：AdjustDown 建的是大堆

Heap.h 里的 AdjustDown 比较方向是 a[child] > a[parent]，建的是大堆。而"求前 K 大"需要的是小堆。直接拿来用会发生什么：

1. 建出来的是大堆，堆顶是这 K 个数里的最大值；
2. 筛选条件是 a[i] > kminheap[0]，也就是"比堆顶大才准进来"；
3. 而堆顶已经是最大了，新元素不可能比它更大 → 一个都进不来。

函数照常编译、照常运行、照常打印，输出的却是最初那 K 个数。没有报错，没有崩溃，只有错。

所以得单独写一份小堆版：

// 小堆版向下调整：比较方向与大堆版相反
void AdjustDownSmall(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;
    }
}

对照大堆版记：两个 < 全部换成 >，其余一个字都不改。这一点值得单独默写一遍，因为它是最容易"写对了但写反了"的地方。

数组版：PrintTopK

void PrintTopK(int* a, int n, int k)
{
    assert(a);
    assert(k > 0 && k <= n);

    // 1. 用 a 中前 k 个元素建小堆
    int* kminheap = (int*)malloc(sizeof(int) * k);
    if (kminheap == NULL)
    {
        perror("malloc fail");
        return;
    }
    for (int i = 0; i < k; i++)
    {
        kminheap[i] = a[i];
    }
    for (int i = (k - 1 - 1) / 2; i >= 0; i--)
    {
        AdjustDownSmall(kminheap, k, i);
    }

    // 2. 用 a[k] ~ a[n-1] 依次与堆顶比较
    for (int i = k; i < n; i++)
    {
        if (a[i] > kminheap[0])      // 打得过守门人
        {
            kminheap[0] = a[i];      // 替换堆顶
            AdjustDownSmall(kminheap, k, 0);
        }
    }

    // 3. 输出
    for (int i = 0; i < k; i++)
    {
        printf("%d ", kminheap[i]);
    }
    printf("\n");

    free(kminheap);
}

assert(k > 0 && k <= n) 这一行不是装饰：k > n 时前 K 个元素根本取不满，k = 0 时 (k-1-1)/2 会算成负数下标。参数校验放在函数入口，是《高质量C++/C编程指南》规则 6-3-1 的要求。

配套的测试函数（课件原样）：

void TestTopk()
{
    int n = 10000;
    int* a = (int*)malloc(sizeof(int) * n);
    srand(time(0));
    for (size_t i = 0; i < n; ++i)
    {
        a[i] = rand() % 1000000;
    }
    a[5]     = 1000000 + 1;
    a[1231]  = 1000000 + 2;
    a[531]   = 1000000 + 3;
    a[5121]  = 1000000 + 4;
    a[115]   = 1000000 + 5;
    a[2335]  = 1000000 + 6;
    a[9999]  = 1000000 + 7;
    a[76]    = 1000000 + 8;
    a[423]   = 1000000 + 9;
    a[3144]  = 1000000 + 10;
    PrintTopK(a, n, 10);
}

测试思路很实用：先用 rand() % 1000000 生成一万个小于 100 万的随机数，再手工把 10 个位置改成 100 万以上。这样一来正确答案是已知的——如果程序输出的正是 1000010 到 1000001 这十个数，说明筛选逻辑没错。

文件版：数据根本不在内存里

数组版要求整个 a 都在内存里。Top-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) % 10000000;
        fprintf(fin, "%d\n", x);
    }

    fclose(fin);
}

再筛选：

void TestHeap3()
{
    int k;
    printf("请输入k>:");
    scanf("%d", &k);
    int* kminheap = (int*)malloc(sizeof(int) * k);
    if (kminheap == NULL)
    {
        perror("malloc fail");
        return;
    }
    const char* file = "data.txt";
    FILE* fout = fopen(file, "r");
    if (fout == NULL)
    {
        perror("fopen error");
        return;
    }

    // 读取文件中前k个数
    for (int i = 0; i < k; i++)
    {
        fscanf(fout, "%d", &kminheap[i]);
    }

    // 建K个数的小堆
    for (int i = (k - 1 - 1) / 2; i >= 0; i--)
    {
        AdjustDownSmall(kminheap, k, i);
    }

    // 读取剩下的N-K个数
    int x = 0;
    while (fscanf(fout, "%d", &x) > 0)
    {
        if (x > kminheap[0])
        {
            kminheap[0] = x;
            AdjustDownSmall(kminheap, k, 0);
        }
    }

    printf("最大前%d个数：", k);
    for (int i = 0; i < k; i++)
    {
        printf("%d ", kminheap[i]);
    }
    printf("\n");
}

三个值得停下来的地方。

一、while (fscanf(fout, "%d", &x) > 0) —— 内存里始终只有 k 个数。

fscanf 一次只搬一个数进内存：读进来、比一下、不要就丢，再读下一个。整个文件从头到尾只顺序扫一遍，峰值内存 = k 个 int，与 N 无关。

这就是前面那个"4 GB 问题"的答案：

	方案	峰值内存	时间
排序	全部读进来再排	O(N) — 10 亿个数要 4 GB	O(N log N)
小堆筛选	边读边筛	O(K) — 1000 个数要 4 KB	O(N log K)

10 亿个数时 log₂N ≈ 30、log₂K ≈ 10，时间上快 3 倍。但真正决定成败的是内存那一列：4 GB 根本分配不出来，快多少倍都没有意义。

fscanf 读到文件尾返回 EOF（值为 -1），循环退出——用返回值当循环条件，顺便把"读到尾"这件事也处理了。

二、(rand() + i) % 10000000 里的 + i。

只写 rand() % 10000000 也能跑。加 i 是为了打散某些实现里 rand() 输出模式的规律性，让数据更接近真实分布。造测试数据的代码也值得较真——数据不合格，从它得出的结论就不合格。

三、这段代码没有 fclose(fout)，也没有 free(kminheap)。

两个资源都漏了。这不是小事，后面「常见误区」单独说。

结果是有序的吗

TestHeap3 输出的是前 K 大的数，但顺序是乱的。

它给出的是一份"谁在榜上"的名单，不是排行榜。小堆只保证一件事：堆顶是这 K 个里最小的。堆内其余元素的相对顺序没有任何保证——这正是「误区五」讲的：堆不是有序序列。

想把名单变成从大到小的排行榜，还得再走一步：

void PrintTopKSorted(int* kminheap, int k)
{
    // TODO(human): 把 kminheap 里这 k 个数按"从大到小"输出。
    //             提示：kminheap 是一个小堆，堆顶是其中最小的那个。
}

💡 这里有个取舍要自己拿主意：k 很小时，直接 qsort 更快也更短；k 接近 N 时，用堆排序的思路原地排完更省内存。两条路都通向正确答案，选哪条取决于 k 和 N 的相对大小。

这就是笔记里"堆外排序"的雏形：筛选在内存外，排序在内存内。K 个数一旦进了内存，怎么排都便宜；真正困难的部分（遍历 N 个数）已经在上一阶段用 O(K) 的空间解决了。

复杂度不是纸面数字

课堂上有一次很实在的对比。以 N = 1000 为例：

算法	运算量
堆排序 O(N log N)	1000 × 10 = 1 万次
冒泡排序 O(N²)	1000 × 1000 = 100 万次

差了 100 倍。但这里有个反直觉的结论：这个差距在实际运行中感觉不到。因为 CPU 每秒执行上亿次运算，1 万次和 100 万次都是瞬间跑完的。

把 N 换成 100 万，差距才开始咬人：

算法	运算量	感受
堆排序	100 万 × 20 = 2000 万	每秒上亿次，一瞬间
冒泡排序	100 万 × 100 万 = 1 万亿	每秒 1 亿次也要 1 万秒

课堂上现场跑过对比（同一组随机数据）：

• 10 万个数据，堆排序 30 毫秒；
• 10 万个数据，冒泡排序（Release 版）9 秒。

差了整整两个数量级还多。所以"冒泡排序在实践中只有教学意义"这句话，不是夸张。

这也顺带回答了前面所有铺垫的意义：树的概念 → 完全二叉树 → 用数组存 → 调堆，绕这么大一圈，都是为了效率。

链式二叉树

前面 3.x 全是顺序结构。但顺序结构只适合完全二叉树，一般二叉树得用链式结构存——这部分是二叉树的另一半。

前置说明

学习二叉树的基本操作之前，得先有一棵二叉树。真正"从数组构建二叉树"的方法要放到后面讲，这里先手工连一棵，把精力集中在操作上：

typedef int BTDataType;

typedef struct BinaryTreeNode
{
    BTDataType _data;
    struct BinaryTreeNode* _left;
    struct BinaryTreeNode* _right;
} BTNode;

BTNode* CreatBinaryTree()
{
    BTNode* node1 = BuyNode(1);
    BTNode* node2 = BuyNode(2);
    BTNode* node3 = BuyNode(3);
    BTNode* node4 = BuyNode(4);
    BTNode* node5 = BuyNode(5);
    BTNode* node6 = BuyNode(6);

    node1->_left = node2;
    node1->_right = node4;
    node2->_left = node3;
    node4->_left = node5;
    node4->_right = node6;

    return node1;
}

⚠️ 这不是创建二叉树的常规方式。它只是教学脚手架——等二叉树结构摸熟了，再回头研究真正的创建方式。

遍历：前序、中序、后序

二叉树遍历（Traversal）：按照某种特定的规则，依次对二叉树中的每个结点进行相应的操作，并且每个结点只操作一次。遍历是二叉树上最重要的运算之一，也是二叉树上进行其他运算的基础。

按"访问根结点"发生在什么时候，分为三种递归遍历：

遍历	访问根结点的时机	记号	别称
前序遍历（Preorder Traversal）	遍历左右子树之前	NLR	先根遍历
中序遍历（Inorder Traversal）	遍历左右子树之中	LNR	中根遍历
后序遍历（Postorder Traversal）	遍历左右子树之后	LRN	后根遍历

接口：

// 二叉树前序遍历
void PreOrder(BTNode* root);
// 二叉树中序遍历
void InOrder(BTNode* root);
// 二叉树后序遍历
void PostOrder(BTNode* root);

N、L、R 分别解释为 Node（根）、Left subtree（左子树）、Right subtree（右子树）。

为什么三种遍历都要递归？因为二叉树的定义本来就是递归的：空树，或者根结点 + 左子树 + 右子树。定义递归，操作自然递归。

上面 CreatBinaryTree 建出的树，三种遍历结果：

前序遍历结果：1 2 3 4 5 6
中序遍历结果：3 2 1 5 4 6
后序遍历结果：3 2 5 6 4 1

值得自己推一遍：前序是"根 → 左 → 右"，所以先出根 1，再整棵左子树，再整棵右子树；中序是"左 → 根 → 右"，所以 1 被夹在中间；后序是"左 → 右 → 根"，所以 1 出现在最后。

层序遍历

除上述三种外还有层序遍历：设根结点所在层数为 1，从根结点出发，先访问第一层的根结点，然后从左到右访问第 2 层的结点，接着第 3 层……自上而下、自左至右逐层访问。

// 层序遍历
void LevelOrder(BTNode* root);

注意：层序遍历不用递归，它要用队列——出队一个结点，就把它的左右孩子依次入队。这也解释了为什么栈和队列要先学。

五道练习题

1. 某完全二叉树按层次输出（同一层从左到右）的序列为 ABCDEFGH，该完全二叉树的前序序列为（ ）
   A ABDHECFG　B ABCDEFGH　C HDBEAFCG　D HDEBFGCA
2. 二叉树的先序遍历和中序遍历如下：先序遍历 EFHIGJK，中序遍历 HFIEJKG，则二叉树根结点为（ ）
   A E　B F　C G　D H
3. 设一棵二叉树的中序遍历序列为 badce，后序遍历序列为 bdeca，则二叉树前序遍历序列为（ ）
   A adbce　B decab　C debac　D abcde
4. 某二叉树的后序遍历序列与中序遍历序列相同，均为 ABCDEF，则按层次输出（同一层从左到右）的序列为（ ）
   A FEDCBA　B CBAFED　C DEFCBA　D ABCDEF

答案：1.A　2.A　3.D　4.A

解析的关键在于根结点在哪：

• 第 2 题最直接：先序遍历的第一个结点就是根，所以根是 E。
• 第 3 题：后序遍历的最后一个结点是根，根是 a；回到中序 badce，a 左边是 b（左子树），右边是 dce（右子树）；对 dce 重复同样的动作，逐层剥离。
• 第 4 题是个信号题：后序和中序完全相同 → 这棵树没有右子树，逐层剥下去会得到一条左斜的链，层序输出即为 A。

📖 参考：《数据结构知识库》第四节 · 二叉树 —— “中序 + 前序（或中序 + 后序）可唯一确定一棵二叉树；只有前序 + 后序不行”。上面第 1~3 题都是这个原理的直接应用。

结点个数、高度与查找

// 二叉树结点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子结点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);

这四个函数是**分治（Divide and Conquer）**的入门练习：把"整棵树的问题"拆成"左子树的问题 + 右子树的问题"，各自递归求解后合并。

创建与销毁

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi);
// 二叉树销毁
void BinaryTreeDestory(BTNode** root);
// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root);

两个参数值得看一眼：

• BinaryTreeCreate 里字符串中的 # 表示空结点，用前序遍历的顺序把树"序列化"下来，再反序列化回去。int* pi 是遍历位置的下标——递归中要共享同一个位置，所以必须传指针。
• BinaryTreeDestory 的参数是 BTNode**，因为销毁后还要把调用方的根指针置空，否则留下悬垂指针。释放不等于置空：free 之后的指针仍指向原地址，只是那块内存已经是垃圾。

📖 参考：《高质量C++/C编程指南》第 7 章 · 内存管理 —— "free/delete 后未置 NULL"被列为典型错误；第 6 章规则 6-3-1 要求函数入口处用 assert 检查参数有效性。

基础 OJ 练习

课件列了七道，前几道是理解递归遍历的直接检验：

1. 单值二叉树
2. 检查两棵树是否相同
3. 对称二叉树
4. 二叉树的前序遍历
5. 二叉树的中序遍历
6. 二叉树的后序遍历
7. 另一棵树的子树

常见误区

误区一：交换函数被局部变量遮蔽

// 错误写法
void Swap(HPDataType* p1, HPDataType* p2)
{
    HPDataType tmp = *p1;
    HPDataType* p2 = p1;    // 重新声明了一个局部变量 p2，形参被遮蔽
    HPDataType* p1 = tmp;   // 把 int 赋给指针，类型不匹配
}

三处问题：

• 第 2 行重新声明了一个局部变量 p2，它和形参没有任何关系，调用方的实参根本没被改到；
• 第 3 行类型完全不匹配（HPDataType* ← HPDataType），编译直接报错；
• 两个局部变量还用了和形参相同的名字，属于"自己覆盖自己"。

正确写法只有三行——要交换的是两个数的值，通过指针访问到的 *p1、*p2，不是指针本身：

// 正确写法
void Swap(HPDataType* p1, HPDataType* p2)
{
    HPDataType tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}

误区二：扩容判断写成自己和自己比较

// 错误写法
if (php->capacity == php->capacity)   // 恒为真

这个条件永远成立，导致每次插入都扩容；如果再顺手写成 php->a = tmp 而没拷贝旧数据，之前存的元素会被整块丢掉。正确的判满是：

if (php->size == php->capacity)   // 有效元素个数 == 容量

排错时先看这类"恒真/恒假"的条件——它们不报错，只是安静地让程序做错事。

误区三：销毁时 free 错了对象

// 错误写法
void HPDestory(HP* php)
{
    free(php);       // 释放的是结构体指针
    php->a = NULL;   // 结构体已经没了，这行是典型的 use-after-free
    php->size = 0;
    php->capacity = 0;
}

如果 HP 是栈上的局部变量，free(php) 释放的是一块不属于堆内存的地址；如果它是 malloc 出来的，那么 php->a 指向的动态数组就永远泄漏了。要释放的是 php->a。

误区四：向上调整里 (child - 1) / 2 的"巧合"

当 child == 0 时，(0 - 1) / 2 在数学上是 -0.5，但整数除法向零截断，结果是 0 而不是负数。

后果是：如果循环条件写成 parent >= 0，parent 永远不可能变成负数，循环会原地打转。

// 危险：依赖整除的巧合，逻辑上不成立
while (parent >= 0)
{
    ...
    parent = (child - 1) / 2;
}

// 稳妥：用子结点下标大于 0 作为继续条件
while (child > 0)
{
    ...
    parent = (child - 1) / 2;
}

while (child > 0) 的语义是清晰的——“当前结点不是根，就继续往上比”。即使整数除法的行为和预期不一致，循环照样能正确退出。

写代码时如果出现"这样写竟然也能跑对"的情况，去怀疑它。能跑不等于对，这类巧合在换一种数据分布或换一个平台时就会崩。

误区五：以为堆是有序序列

堆只保证父子之间的大小关系，兄弟之间没有任何约定。同一个堆，左右孩子互换后仍然是合法的堆。

由此派生两条常见的错误认知：

• 看到大堆堆顶是最大值，就以为 a[1] 就是次大值——不成立；
• 以为"堆排序就是把堆建好后逐层读出来"——不行，层序读出来只是层序序列，不是排序结果。

误区六：Top-K 里把堆的方向用反了

"求前 K 大"要建小堆——这一点和直觉相反，也和 Heap.h 里现成的 AdjustDown（建大堆）相反。

目标	建什么堆	堆顶是谁
前 K 大	小堆	这 K 个里最小的
前 K 小	大堆	这 K 个里最大的

记住"堆顶是守门人"这个画面就不会错：堆顶必须是这 K 个里最没资格的那一个——新元素只要能打败它，就证明它比榜上某个人更该留下。求前 K 大时，"最没资格"的正是最小的那个，所以建小堆。

而 AdjustDown 建的是大堆。直接拿它来用，筛选条件 a[i] > 堆顶 永远为假，一个元素都换不进来，函数却正常返回。这是最难查的一类错误：没有崩溃，没有报错，只是答案是错的。

误区七：文件句柄和内存都没还回去

TestHeap3 里申请了两个资源，一个都没还：

FILE* fout = fopen(file, "r");      // 没有对应的 fclose(fout)
int* kminheap = (int*)malloc(...);  // 没有对应的 free(kminheap)

函数返回时进程会回收它们，所以"跑一次"看不出任何问题。但这两个洞是真实的：

• 文件句柄是有限资源。操作系统对单进程同时打开的文件数有上限（常见是 1024）。这段逻辑一旦放进循环，很快就会出现 fopen 失败。
• 堆内存不会自己回来。在同一进程里反复调用，占用持续增长。

补上只是两行：

    free(kminheap);
    fclose(fout);

📖 参考：《高质量C++/C编程指南》第 7 章 · 内存管理 —— “申请了就要释放，释放后置 NULL”。这里的文件句柄在原文中没有直接对应条目，但道理完全相同：资源不只有内存，任何需要归还的东西都算。

本节要点

• 树的定义是递归的：树 = 根结点 + N 棵互不相交的子树。子树之间有交集就不是树。
• 二叉树是有序树：左右不可互换，且不存在度大于 2 的结点。
• n0 = n2 + 1：从"结点总数"和"边总数"两个视角列方程联立得到，能秒杀一大类选择题。
• 同层数下结点数有上下界：满二叉树 n = 2^h − 1（h = log₂(n+1)）；完全二叉树最少 n = 2^(h−1)（h = log₂n + 1），两者差一倍。完全二叉树的 n1 只能是 0 或 1——n1 = 1 时结点总数必为偶数。
• 顺序存储只适合完全二叉树：只有完全二叉树按层序存进数组才没有空洞，下标公式 (i−1)/2、2i+1、2i+2 才成立。
• 堆 = 完全二叉树 + 父子有序：兄弟无序，所以堆不是有序序列；数据结构里的"堆"也不是操作系统的"堆区"。
• 向下调整的前提是左右子树已经是堆，用 child < n 判断是否到叶子；向上调整的循环条件用 child > 0，不要依赖整数除法的巧合。
• 删除堆顶用首尾交换 + 向下调整，不能直接删——否则兄弟变父子，结构全乱。取堆顶 O(1)，插入删除 O(log N)。
• 建堆有两种：向上调整建堆 O(N log N)；向下调整建堆（从最后一个非叶子结点倒着调）是 O(N)。
• 升序建大堆，降序建小堆，每轮把堆顶换到数组末尾——换成开头会破坏堆的结构，代价是重新建堆。
• Top-K 用大小为 K 的堆：求前 K 大建小堆，求前 K 小建大堆——堆顶永远是这 K 个里"最没资格"的那个（守门人）。时间 O(N log K)，空间 O(K)，与 N 无关。
• AdjustDown 建的是大堆：Top-K 需要小堆时必须另写一份小堆版（把两个 < 换成 >）。方向反了不会报错，只会静默给出错误答案——这类错误比崩溃难查得多。
• 数据在文件里时边读边筛：while (fscanf(fout, "%d", &x) > 0) 一次只搬一个数进内存，峰值内存 O(K)。N = 10 亿时排序要 4 GB，小堆筛选只要 4 KB。筛选完的 K 个数是无序名单，要排行榜还得再排一次（即"堆外排序"）。
• 申请的资源都要还：malloc 配 free，fopen 配 fclose。文件句柄同样是有限的（单进程常见上限 1024），漏掉它比漏掉内存更早出问题。
• 链式二叉树的遍历：前序/中序/后序靠递归（定义就是递归的），层序靠队列；中序 + 前序（或中序 + 后序）可唯一确定一棵二叉树。
• 复杂度要落到量级上：N = 1000 时 O(N log N) 和 O(N²) 的差距感觉不到，N = 100 万时是 2000 万次对 1 万亿次——10 万数据实测 30 ms 对 9 s。

---

📖 参考：《数据结构知识库》第四、七节
📖 参考：《高质量C++/C编程指南》第 6、7 章

---

*KIRACRIMSON