从二叉树到堆：树遍历、堆排序与前K个数据-171主机测评

前面学习链表时，我们已经接触过一种很重要的思想：节点不一定要连续存放，只要通过指针把它们连接起来，就可以组织成一个数据结构。

二叉树也是由节点和指针组成的。不过，链表中的一个节点通常只有一个后继节点，而二叉树中的一个节点最多可以连接两个孩子：左孩子和右孩子。

刚开始接触二叉树时，最容易出现两个问题：

只会背“前序、中序、后序”，却不知道递归调用到底是怎样走的；

看到堆排序和 Top K，就只记住代码，遇到下标、边界和大小堆方向就容易写错。

所以这篇文章不从复杂的树结构开始，而是从最基本的二叉树出发，一步一步解决这些问题：

二叉树是什么，节点之间有哪些数量关系；
满二叉树和完全二叉树有什么区别；
前序、中序、后序遍历如何写递归版和迭代版；
为什么迭代遍历需要栈，层序遍历需要队列；
堆为什么可以用数组表示；
大堆和小堆分别适合什么场景；
堆排序为什么升序使用大堆；
数据量非常大、内存空间很小时，怎样找出前 K 大或前 K 小的数据。

本文只讨论普通二叉树和堆，不扩展到其他还没有学习的树结构。

一、二叉树到底是什么

二叉树是一种树形结构。它有一个根节点，每个节点最多有两个孩子，分别称为左孩子和右孩子。

这里的“二”表示最多有两个，并不是每个节点必须有两个孩子。一个节点可能有：

没有孩子；
只有左孩子；
只有右孩子；
同时有左孩子和右孩子。

例如：

A
/ \\
B C
/ \\
D E

在这棵树中：

A 是根节点；
B 和 C 是 A 的孩子；
A 是 B 和 C 的父节点；
B 和 C 是兄弟节点；
D 和 E 没有孩子，所以它们是叶子节点；
A 和 B 是非叶子节点。

二叉树的左孩子和右孩子是有区别的：

A A
/ \\
B B

虽然两棵树中都有 A 和 B，但第一棵树里 B 是左孩子，第二棵树里 B 是右孩子，因此结构并不相同。

根、层数和高度

本文规定根节点所在的位置为第 1 层。

A 第1层
/ \\
B C 第2层
/ \\
D E 第3层

树中最大的层数称为树的高度。上面这棵树的高度就是 3。

有些资料把根节点记为第 0 层，这样高度公式会相差 1。两种定义都可以，关键是整篇推导必须使用同一种定义。下面全部按照“根节点为第 1 层”计算。

二、二叉树中节点数量的关系

二叉树的很多题目不是直接让我们写代码，而是让我们根据节点数量求叶子节点数量，或者根据高度求最多节点数。

如果只背公式，题目一变就容易混乱。下面从边的数量开始推导。

设：

n0：度为0的节点数量，也就是叶子节点数量
n1：度为1的节点数量
n2：度为2的节点数量
n ：总结点数量

每个节点只能属于这三类中的一类，所以：

n = n0 + n1 + n2

1. 一棵非空树有多少条边

除了根节点以外，每个节点都有一个父节点。每个非根节点都对应一条从父节点指向自己的边。

因此，一棵有 n 个节点的非空树，一定有：

n – 1 条边

例如有 6 个节点，就有 5 条边。根节点没有父节点，所以少一条。

2. 从父节点的角度统计边

换一个角度看，每个节点可以贡献一定数量的孩子边：

度为 0 的节点贡献 0 条边；
度为 1 的节点贡献 1 条边；
度为 2 的节点贡献 2 条边。

所以边的数量还可以写成：

n1 + 2n2

两种方法统计的是同一棵树的边，因此：

n – 1 = n1 + 2n2

又因为：

n = n0 + n1 + n2

把它代入前面的式子：

n0 + n1 + n2 – 1 = n1 + 2n2

消去两边的 n1：

n0 + n2 – 1 = 2n2

继续整理：

n0 – 1 = n2

所以得到：

n0 = n2 + 1

也就是说：

在任何一棵非空二叉树中，叶子节点数量一定比度为 2 的节点数量多 1。

注意，这个关系和度为 1 的节点数量没有关系。无论树中有多少个只有一个孩子的节点，这个关系都成立。

3. 用一棵树验证

A
/ \\
B C
/ \\ \\
D E F

这棵树中：

n0 = 3，叶子节点是 D、E、F
n1 = 1，度为1的节点是 C
n2 = 2，度为2的节点是 A、B

验证公式：

n0 = n2 + 1
3 = 2 + 1

公式成立。

这个公式的前提是二叉树非空。空树没有根节点，不能直接使用“边数为 n – 1”的推导。

三、每层最多有多少个节点

仍然规定根节点是第 1 层。

第 1 层最多有 1 个节点：

1 = 2^0

第 2 层最多有 2 个节点：

2 = 2^1

第 3 层最多有 4 个节点：

4 = 2^2

因为每个节点最多产生两个孩子，所以第 i 层最多有：

2^(i – 1) 个节点

如果一棵树的高度为 h，并且每一层都达到最多数量，那么总节点数为：

1 + 2 + 4 + … + 2^(h – 1)

这是等比数列，求和结果为：

2^h – 1

所以：

高度为 h 的二叉树，最多有 2^h – 1 个节点。

例如高度为 3：

2^3 – 1 = 7

确实最多有 7 个节点。

高度为 h 时最少有多少个节点

只要每层保留一个节点，就可以形成一条链：

A
\\
B
\\
C
\\
D

这棵树高度为 4，节点数量也是 4。因此高度为 h 的二叉树至少有 h 个节点。

所以高度为 h 的二叉树，节点数范围是：

h <= n <= 2^h – 1

这也说明了二叉树的形状可能差别很大：它既可以接近一条链，也可以每层都排满。

四、满二叉树和完全二叉树

1. 满二叉树

一棵二叉树的每一层都达到最大节点数，这棵树就是满二叉树。

高度为 3 的满二叉树如下：

A
/ \\
B C
/ \\ / \\
D E F G

它的每一层分别有：

第1层：1个
第2层：2个
第3层：4个

总结点数为：

1 + 2 + 4 = 7

也就是：

2^3 – 1 = 7

满二叉树还有一个特点：除叶子节点外，每个节点都有两个孩子，并且所有叶子节点都在同一层。

2. 完全二叉树

完全二叉树的要求是：

除最后一层外，其他层都必须排满；

最后一层的节点必须从左到右连续排列，中间不能有空位。

例如：

A
/ \\
B C
/ \\ /
D E F

它的最后一层虽然没有排满，但节点 D、E、F 是从左到右连续排列的，所以它是完全二叉树。

下面这棵树不是完全二叉树：

A
/ \\
B C
\\ /
E F

B 没有左孩子却有右孩子，左侧出现了空位，破坏了连续排列的要求。

还要注意：

满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。

3. 完全二叉树的高度

高度为 h 的完全二叉树，前 h – 1 层一定是满的，所以前面共有：

1 + 2 + … + 2^(h – 2)
= 2^(h – 1) – 1

最后一层至少有 1 个节点，最多有 2^(h – 1) 个节点。因此总结点数满足：

2^(h – 1) <= n <= 2^h – 1

由此可以得到完全二叉树的高度：

h = floor(log2(n)) + 1

例如 n = 6：

floor(log2(6)) + 1
= 2 + 1
= 3

所以 6 个节点的完全二叉树高度为 3。

五、用 C 语言表示二叉树

普通二叉树的形状不固定，用数组表示可能会产生很多空位置，所以通常使用链式结构。

typedef struct Node
{
char data;
struct Node* left;
struct Node* right;
} Node;

每个节点中保存：

当前节点的数据；
左孩子的地址；
右孩子的地址。

创建节点：

Node* create_node(char data)
{
Node* node = (Node*)malloc(sizeof(Node));
if (node == NULL)
{
printf("malloc failed\\n");
exit(1);
}

node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}

这里使用 malloc 申请节点空间，所以最后必须使用 free 释放。

为了演示遍历，我们手动构造下面这棵树：

A
/ \\
B C
/ \\ \\
D E F

Node* create_tree(void)
{
Node* a = create_node('A');
Node* b = create_node('B');
Node* c = create_node('C');
Node* d = create_node('D');
Node* e = create_node('E');
Node* f = create_node('F');

a->left = b;
a->right = c;
b->left = d;
b->right = e;
c->right = f;

return a;
}

这段代码只是构造测试树，不是从输入序列自动建树的通用方法。

六、二叉树的三种遍历

三种遍历的区别，只在于根节点什么时候访问。

前序：根、左、右
中序：左、根、右
后序：左、右、根

还是使用下面这棵树：

A
/ \\
B C
/ \\ \\
D E F

三种遍历结果如下：

前序：A B D E C F
中序：D B E A C F
后序：D E B F C A

“前、中、后”说的是根节点相对于左右子树的位置。

七、三种遍历的递归写法

二叉树特别适合递归，是因为一棵二叉树的左子树和右子树仍然是二叉树。

写递归函数时，要先确定两个问题：

什么时候结束；

当前节点应该放在两次递归调用的什么位置。

1. 前序遍历

void preorder(Node* root)
{
if (root == NULL)
{
return;
}

printf("%c ", root->data);
preorder(root->left);
preorder(root->right);
}

访问 A 时，先打印 A，然后递归处理 B，最后递归处理 C，所以是根、左、右。

2. 中序遍历

void inorder(Node* root)
{
if (root == NULL)
{
return;
}

inorder(root->left);
printf("%c ", root->data);
inorder(root->right);
}

这里把打印根节点放在两次递归调用中间，因此变成左、根、右。

3. 后序遍历

void postorder(Node* root)
{
if (root == NULL)
{
return;
}

postorder(root->left);
postorder(root->right);
printf("%c ", root->data);
}

后序遍历中，根节点最后访问，所以特别适合释放整棵树：先释放孩子，再释放自己。

void destroy_tree(Node* root)
{
if (root == NULL)
{
return;
}

destroy_tree(root->left);
destroy_tree(root->right);
free(root);
}

如果先释放当前节点，再访问：

root->left
root->right

就会访问已经释放的内存，产生未定义行为。

4. 递归遍历的复杂度

每个节点只访问一次，所以三种递归遍历的时间复杂度都是：

O(n)

空间复杂度不是 O(1)。递归调用会占用函数调用栈，最多同时保存从根节点到当前节点的一条路径，所以空间复杂度是：

O(h)

其中 h 是树的高度。

如果树接近完全二叉树，h 大约是 log n；如果树退化成链，h 就等于 n。因此最坏空间复杂度为 O(n)。

八、为什么要写迭代版本

递归代码短，而且符合二叉树的定义，但递归深度太大时会占用很多调用栈空间。

迭代版本不再依赖系统自动保存调用过程，而是自己使用栈来保存“以后还要处理的节点”。这也是理解递归和栈之间关系的一个好例子：

递归调用隐藏了栈，迭代写法把这个栈明确写了出来。

为了让代码更容易理解，先定义一个保存节点指针的栈。

typedef struct Stack
{
Node** data;
int size;
int capacity;
} Stack;

初始化栈：

void stack_init(Stack* stack)
{
stack->capacity = 8;
stack->size = 0;
stack->data = (Node**)malloc(
sizeof(Node*) * stack->capacity);

if (stack->data == NULL)
{
printf("malloc failed\\n");
exit(1);
}
}

入栈：

void stack_push(Stack* stack, Node* node)
{
if (stack->size == stack->capacity)
{
stack->capacity *= 2;
Node** new_data = (Node**)realloc(
stack->data,
sizeof(Node*) * stack->capacity);

if (new_data == NULL)
{
free(stack->data);
printf("realloc failed\\n");
exit(1);
}

stack->data = new_data;
}

stack->data[stack->size] = node;
stack->size++;
}

出栈和查看栈顶：

Node* stack_pop(Stack* stack)
{
if (stack->size == 0)
{
return NULL;
}

stack->size—;
return stack->data[stack->size];
}

Node* stack_top(Stack* stack)
{
if (stack->size == 0)
{
return NULL;
}

return stack->data[stack->size – 1];
}

int stack_empty(Stack* stack)
{
return stack->size == 0;
}

void stack_destroy(Stack* stack)
{
free(stack->data);
stack->data = NULL;
stack->size = 0;
stack->capacity = 0;
}

这里有一个容易忽略的细节：栈中保存的是 Node*，释放栈数组并不等于释放树节点。栈只是暂时保存节点地址，树节点仍然由 destroy_tree 负责释放。

1. 前序遍历的迭代版

前序顺序是：

根 -> 左 -> 右

访问一个节点后，应该先处理左孩子，再处理右孩子。但栈是后进先出，所以要先压入右孩子，再压入左孩子。

void preorder_loop(Node* root)
{
if (root == NULL)
{
return;
}

Stack stack;
stack_init(&stack);
stack_push(&stack, root);

while (!stack_empty(&stack))
{
Node* cur = stack_pop(&stack);
printf("%c ", cur->data);

if (cur->right != NULL)
{
stack_push(&stack, cur->right);
}

if (cur->left != NULL)
{
stack_push(&stack, cur->left);
}
}

stack_destroy(&stack);
}

为什么不能先压左孩子？

假设当前节点是 A：

先压左孩子 B
再压右孩子 C

由于 C 后入栈，下一次会先弹出 C，结果就变成根、右、左，顺序错误。

2. 中序遍历的迭代版

中序遍历要求左子树全部处理完之后，才能访问当前节点。因此不能像前序一样弹出节点就直接打印。

正确思路是：

沿着左孩子一直向下；

把经过的节点全部压栈；

走到空节点后，弹出栈顶并访问；

转向这个节点的右子树。

void inorder_loop(Node* root)
{
Stack stack;
stack_init(&stack);

Node* cur = root;

while (cur != NULL || !stack_empty(&stack))
{
while (cur != NULL)
{
stack_push(&stack, cur);
cur = cur->left;
}

cur = stack_pop(&stack);
printf("%c ", cur->data);
cur = cur->right;
}

stack_destroy(&stack);
}

外层循环必须使用“或者”：

cur != NULL || !stack_empty(&stack)

因为 cur == NULL 只表示当前这条左路走完了，栈中可能还保存着等待访问的父节点。

如果把条件误写成：

cur != NULL && !stack_empty(&stack)

走到最左边的空节点时，cur 已经是空指针，循环会提前结束，甚至一个节点都打印不出来。

弹出当前节点并打印以后，还必须执行：

cur = cur->right;

因为中序顺序是左、根、右。当前节点已经完成左子树和自身访问，下一步就是右子树。

3. 后序遍历的迭代版

后序遍历是三种遍历中最容易写错的：

左 -> 右 -> 根

当一个节点出现在栈顶时，不能马上访问它，因为它的右子树可能还没有处理。

可以使用一个指针 last 记录上一次访问完成的节点：

void postorder_loop(Node* root)
{
Stack stack;
stack_init(&stack);

Node* cur = root;
Node* last = NULL;

while (cur != NULL || !stack_empty(&stack))
{
while (cur != NULL)
{
stack_push(&stack, cur);
cur = cur->left;
}

Node* top = stack_top(&stack);

if (top->right != NULL && top->right != last)
{
cur = top->right;
}
else
{
printf("%c ", top->data);
last = stack_pop(&stack);
}
}

stack_destroy(&stack);
}

这段代码的关键在于：

if (top->right != NULL && top->right != last)

它表示：

如果当前节点有右子树；
并且这个右子树还不是刚刚处理完的那棵树；
那么先转向右子树。

如果 top->right == last，说明右子树已经处理完了，此时才能访问当前节点。

例如处理 B：

第一次回到 B：右孩子 E 还没有处理，转向 E
处理完 E：last 指向 E
再次回到 B：B 的右孩子就是 last，可以访问 B

如果没有 last 判断，程序会在 B 和 E 之间反复进入，形成死循环。

九、层序遍历和队列

前序、中序、后序都是沿着树的高度向下走，属于深度优先遍历。

如果希望按照从上到下、从左到右的顺序访问，就需要层序遍历：

A B C D E F

层序遍历适合使用队列。访问 A 后，把 B 和 C 放到队尾；接着取出 B，再把它的孩子放到后面。先进队列的节点会先被处理。

先定义一个简单的循环队列：

typedef struct Queue
{
Node** data;
int front;
int size;
int capacity;
} Queue;

核心操作如下：

void queue_init(Queue* queue)
{
queue->capacity = 8;
queue->front = 0;
queue->size = 0;
queue->data = (Node**)malloc(
sizeof(Node*) * queue->capacity);

if (queue->data == NULL)
{
printf("malloc failed\\n");
exit(1);
}
}

int queue_empty(Queue* queue)
{
return queue->size == 0;
}

void queue_push(Queue* queue, Node* node)
{
if (queue->size == queue->capacity)
{
int new_capacity = queue->capacity * 2;
Node** new_data = (Node**)malloc(
sizeof(Node*) * new_capacity);

if (new_data == NULL)
{
printf("malloc failed\\n");
exit(1);
}

for (int i = 0; i < queue->size; i++)
{
int index = (queue->front + i) % queue->capacity;
new_data[i] = queue->data[index];
}

free(queue->data);
queue->data = new_data;
queue->capacity = new_capacity;
queue->front = 0;
}

int tail = (queue->front + queue->size)
% queue->capacity;
queue->data[tail] = node;
queue->size++;
}

Node* queue_pop(Queue* queue)
{
if (queue_empty(queue))
{
return NULL;
}

Node* node = queue->data[queue->front];
queue->front = (queue->front + 1) % queue->capacity;
queue->size—;
return node;
}

void queue_destroy(Queue* queue)
{
free(queue->data);
queue->data = NULL;
queue->front = 0;
queue->size = 0;
queue->capacity = 0;
}

层序遍历：

void level_order(Node* root)
{
if (root == NULL)
{
return;
}

Queue queue;
queue_init(&queue);
queue_push(&queue, root);

while (!queue_empty(&queue))
{
Node* cur = queue_pop(&queue);
printf("%c ", cur->data);

if (cur->left != NULL)
{
queue_push(&queue, cur->left);
}

if (cur->right != NULL)
{
queue_push(&queue, cur->right);
}
}

queue_destroy(&queue);
}

这里有两个常见错误：

第一，空树不能把 NULL 放进队列。如果后面访问 cur->data，就会解引用空指针。

第二，孩子入队前必须判断是否为空。队列中只保存真正存在的节点，不保存空指针。

层序遍历的时间复杂度是 O(n)。队列最多保存一层附近的节点，空间复杂度是 O(w)，其中 w 是树的最大宽度；最坏情况下仍然可能达到 O(n)。

十、完全二叉树为什么适合用数组表示

普通二叉树的形状不规则，如果直接用数组存储，可能出现很多空位置。

完全二叉树的节点从上到下、从左到右连续排列，所以可以直接使用数组：

下标：0 1 2 3 4 5
数据：A B C D E F

对应的树是：

A
/ \\
B C
/ \\ /
D E F

如果从 0 开始编号：

左孩子下标 = 2 * 父节点下标 + 1
右孩子下标 = 2 * 父节点下标 + 2
父节点下标 = (孩子下标 – 1) / 2

例如 B 的下标为 1：

左孩子：2 * 1 + 1 = 3，对应 D
右孩子：2 * 1 + 2 = 4，对应 E

例如 F 的下标为 5：

父节点：(5 – 1) / 2 = 2，对应 C

这里使用的是 C 语言整数除法。

下标边界的坑

根节点的下标是 0，它没有父节点，所以不能直接计算：

(0 – 1) / 2

尤其当下标使用无符号类型时，0 – 1 还可能发生下溢，变成一个非常大的数。

因此向上调整时必须先判断：

while (child > 0)

只有不是根节点时，才计算父节点下标。

十一、堆是什么

堆不是普通的二叉树。一个结构要称为堆，必须同时满足两个条件：

形状是完全二叉树；

父节点和孩子节点之间满足大小关系。

1. 大堆

大堆要求每个父节点都不小于自己的孩子：

父节点 >= 左孩子
父节点 >= 右孩子

例如：

9
/ \\
7 8
/ \\ /
3 5 2

数组表示为：

9 7 8 3 5 2

大堆只能保证堆顶是最大值，不能保证整个数组从大到小排列。7 和 8 谁在前面，并不影响大堆性质。

2. 小堆

小堆要求每个父节点都不大于自己的孩子：

父节点 <= 左孩子
父节点 <= 右孩子

例如：

1
/ \\
3 2
/ \\ /
7 5 8

小堆只能保证堆顶是最小值，不能保证整个数组有序。

所以不要把堆误认为排序后的数组：

大堆和小堆只保证父子关系，不保证兄弟节点之间、不同子树之间的完整顺序。

3. 大堆和小堆什么时候使用

如果我们希望快速得到当前最大值，可以使用大堆；如果希望快速得到当前最小值，可以使用小堆。

但是 Top K 问题不能只看“我要找大数还是小数”，而要看堆顶应该保存哪个淘汰门槛：

反复取最大值：大堆
反复取最小值：小堆
找前K大：大小为K的小堆
找前K小：大小为K的大堆

后面会具体说明为什么 Top K 的方向和直觉相反。

十二、堆的向下调整

假设当前节点的左右子树已经分别是大堆，但父节点可能不满足大堆关系：

3
/ \\
7 6
/ \\ /
2 5 1

左右子树都满足大堆，但根节点 3 小于左孩子 7，所以整个结构还不是大堆。

解决方法是让父节点和较大的孩子交换，再继续向下检查。

void adjust_down_max(int* array, int n, int parent)
{
int child = 2 * parent + 1;

while (child < n)
{
if (child + 1 < n
&& array[child + 1] > array[child])
{
child++;
}

if (array[child] > array[parent])
{
int temp = array[parent];
array[parent] = array[child];
array[child] = temp;

parent = child;
child = 2 * parent + 1;
}
else
{
break;
}
}
}

这段代码有几个必须看懂的细节。

1. 为什么先让 child 指向左孩子

下标从 0 开始时，左孩子下标是：

2 * parent + 1

完全二叉树中可能只有左孩子，不可能只有右孩子。因此只要左孩子下标小于 n，就说明至少有一个孩子。

2. 为什么要比较右孩子

大堆中，父节点必须不小于两个孩子。所以应该先选出两个孩子中较大的那个。

例如：

父节点：3
左孩子：5
右孩子：8

如果只和左孩子交换：

5
/ \\
3 8

根节点仍然小于右孩子 8，调整失败。

因此必须先比较：

if (child + 1 < n
&& array[child + 1] > array[child])

这里的 child + 1 < n 必须先判断，确认右孩子下标合法后，才能访问 array[child + 1]。

3. 为什么交换后还要继续向下

父节点向下交换后，到了新的位置，可能仍然小于自己的孩子。因此要让 parent 移动到交换后的位置，再重新计算它的左孩子。

小堆的向下调整完全类似，只需要把“选择较大孩子”和“大于”改成“选择较小孩子”和“小于”。

十三、怎样把数组建成大堆

假设数组为：

4 6 8 5 9 1 3 2

叶子节点没有孩子，单独看一定满足堆的条件。因此建堆时不需要调整叶子节点，只需要从最后一个非叶子节点开始，向前调整到根节点。

最后一个节点下标为：

n – 1

它的父节点下标为：

((n – 1) – 1) / 2
= (n – 2) / 2

所以最后一个非叶子节点下标是：

(n – 2) / 2

建大堆：

void build_max_heap(int* array, int n)
{
if (n < 2)
{
return;
}

for (int parent = (n – 2) / 2;
parent >= 0;
parent—)
{
adjust_down_max(array, n, parent);
}
}

为什么必须从后往前？

因为向下调整有一个前提：当前节点的左右子树已经分别是堆。

从最后一个非叶子节点开始时，它的孩子都是叶子，前提成立。向前处理其他节点时，后面的子树已经调整完成，所以前提仍然成立。

如果从根节点开始，根节点的左右子树还没有建成堆，一次调整不能保证整棵树正确。

建堆的时间复杂度为什么是 O(n)

向下调整一次的最坏时间是 O(log n)，但不能简单地认为有 n 个节点都要走到树底。

完全二叉树中：

大约一半节点是叶子，调整距离为 0；
大约四分之一节点最多向下 1 层；
大约八分之一节点最多向下 2 层；
越靠近根，节点越少。

所以总工作量可以粗略写成：

n/4 * 1 + n/8 * 2 + n/16 * 3 + …

节点数量越多，越靠近叶子的节点越多，而它们的调整距离很短。这个总和的增长速度是线性的，因此从最后一个非叶子节点向前建堆的时间复杂度是：

O(n)

如果把元素一个个插入空堆，每次使用向上调整，那么复杂度通常是 O(n log n)。两种建堆方式不能混在一起计算。

十四、堆排序

现在使用大堆完成升序排序。

升序数组的最后一个位置应该放当前最大值，而大堆的堆顶正好是当前最大值。

每一轮做三件事：

把堆顶和有效区间的最后一个元素交换；

有效区间长度减 1，已经放好的最大值不再参与调整；

对新的堆顶向下调整，恢复大堆。

void heap_sort(int* array, int n)
{
build_max_heap(array, n);

for (int end = n – 1; end > 0; end—)
{
int temp = array[0];
array[0] = array[end];
array[end] = temp;

adjust_down_max(array, end, 0);
}
}

这句非常关键：

adjust_down_max(array, end, 0);

传入的是 end，不是原来的 n。

因为下标 end 位置已经放好了当前最大值，不应该再参与堆调整。如果错误地传入 n，已经排好位置的元素还会被重新放回堆中，排序结果就可能错误。

为什么降序使用小堆

降序数组的最后一个位置应该放当前最小值，所以可以建立小堆，每次把堆顶的最小值交换到有效区间末尾。

因此使用“堆顶和末尾交换”的写法时：

升序：建大堆
降序：建小堆

堆排序的复杂度

建堆需要：

O(n)

之后有 n – 1 轮，每轮向下调整最多需要 O(log n)，所以总时间复杂度为：

O(n log n)

堆排序是在原数组上完成的，除少量临时变量外不需要额外数组，因此额外空间复杂度为：

O(1)

但堆排序不是稳定排序。因为堆顶和数组末尾可能发生远距离交换，相等元素的先后顺序可能发生变化。

十五、堆的遍历

堆本质上是一棵完全二叉树，但实际保存时通常是数组。

直接从下标 0 遍历到 n – 1：

for (int i = 0; i < n; i++)
{
printf("%d ", array[i]);
}

这个顺序对应完全二叉树的层序遍历。

也可以按照数组下标递归访问出前序、中序和后序，例如前序：

void heap_preorder(int* array, int n, int index)
{
if (index >= n)
{
return;
}

printf("%d ", array[index]);
heap_preorder(array, n, 2 * index + 1);
heap_preorder(array, n, 2 * index + 2);
}

不过在堆排序和 Top K 问题中，我们通常并不需要像普通二叉树那样完整遍历堆。堆最重要的用途是快速取得堆顶，并通过向上或向下调整恢复堆的性质。

十六、内存很小，怎样找前 K 大

假设有很多数据，例如一个很大的文件中保存了大量整数，现在要找出其中最大的 100 个数。

如果把所有数据都读入数组再排序：

需要 O(n) 的空间；
排序时间为 O(n log n)；
当数据量超过内存容量时，甚至无法把数组完整创建出来。

这时可以只维护 100 个数据。

1. 前 K 大为什么使用小堆

假设当前已经保存了 3 个最大的数：

70 90 80

把它们建成小堆后，堆顶是 70：

70
/ \\
90 80

这三个数中最小的 70，就是当前进入前 3 大的最低门槛。

新数据到来时：

如果新数据小于等于 70，它不可能进入前 3 大，直接忽略；
如果新数据大于 70，就替换堆顶，再向下调整小堆。

例如新数据是 65：

65 <= 70

直接忽略。

如果新数据是 85：

85 > 70

用 85 替换 70，再调整小堆，保留下来的就是：

80 85 90

所以：

找前 K 大，要维护大小为 K 的小堆，让堆顶保存当前前 K 大中的最小值。

如果错误地使用大堆，堆顶保存的是当前候选中的最大值，无法快速找到“第 K 大”的淘汰门槛。

2. 前 K 大的 C 语言实现

下面的函数把结果放在 result 数组中，结果本身仍然是一个小堆，不保证有序。

void adjust_down_min(int* array, int n, int parent)
{
int child = 2 * parent + 1;

while (child < n)
{
if (child + 1 < n
&& array[child + 1] < array[child])
{
child++;
}

if (array[child] < array[parent])
{
int temp = array[parent];
array[parent] = array[child];
array[child] = temp;

parent = child;
child = 2 * parent + 1;
}
else
{
break;
}
}
}

void build_min_heap(int* array, int n)
{
if (n < 2)
{
return;
}

for (int parent = (n – 2) / 2;
parent >= 0;
parent—)
{
adjust_down_min(array, n, parent);
}
}

int top_k_max(int* array, int n, int k, int* result)
{
if (array == NULL || result == NULL
|| n <= 0 || k <= 0 || k > n)
{
return 0;
}

for (int i = 0; i < k; i++)
{
result[i] = array[i];
}

build_min_heap(result, k);

for (int i = k; i < n; i++)
{
if (array[i] > result[0])
{
result[0] = array[i];
adjust_down_min(result, k, 0);
}
}

return k;
}

函数的处理过程是：

先把前 K 个数放入结果数组；

把结果数组建成小堆；

继续读取剩余数据；

只有新数据大于堆顶时，才替换堆顶并调整；

读完以后，结果数组中保存的就是前 K 大的数据。

如果数据来自文件，可以每次读取一个整数，不必一次性把所有数据放进内存：

读取一个数据
-> 与小堆堆顶比较
-> 必要时替换并调整
-> 读取下一个数据

3. 前 K 小

找前 K 小时，逻辑正好相反。

我们需要快速找到当前前 K 小中最大的那个数，把它作为淘汰门槛。因此要维护大小为 K 的大堆：

前K大：小堆，堆顶是候选中的最小值
前K小：大堆，堆顶是候选中的最大值

4. Top K 的复杂度

初始 K 个元素建堆需要：

O(K)

剩余数据逐个比较，每次真正进入候选集时，向下调整最多需要：

O(log K)

因此最坏时间复杂度为：

O(n log K)

额外空间只保存 K 个候选数据：

O(K)

当 K 远小于 n，并且数据无法一次性装入内存时，这种方法非常合适。

注意，堆中的 K 个结果不一定有序。如果题目要求从大到小或从小到大输出，还需要对这 K 个结果再排序，代价是 O(K log K)。

十七、这些坑最好提前记住

1. 把二叉树理解成每个节点必须有两个孩子

二叉树的节点最多有两个孩子，只有一个孩子或者没有孩子都合法。

2. 忘记空指针结束条件

递归遍历必须先判断：

if (root == NULL)
{
return;
}

否则访问叶子节点的孩子时会解引用空指针。

3. 前序迭代压栈顺序写反

栈是后进先出。想先处理左孩子，就要先压右孩子，再压左孩子。

4. 中序遍历只弹栈，不转向右子树

中序弹出并访问当前节点后，必须执行：

cur = cur->right;

否则右子树会被跳过。

5. 后序遍历弹栈就访问

后序访问当前节点前，必须确认右子树已经处理完成。单栈写法需要记录上一次访问的节点。

6. 只比较左孩子

向下调整时必须先选出两个孩子中更合适的一个：

大堆选较大的孩子；
小堆选较小的孩子。

7. 没有检查右孩子是否存在

访问右孩子前必须判断：

child + 1 < n

否则最后一个父节点只有左孩子时可能越界。

8. 建堆从根节点向后调整

向下调整依赖左右子树已经是堆，所以要从最后一个非叶子节点向前处理。

9. 堆排序的有效区间没有缩小

每轮排好一个元素后，调整范围要使用 end，不能继续使用原来的 n。

10. 把堆当成有序数组

大堆只能保证父节点不小于孩子，小堆只能保证父节点不大于孩子。堆顶之外的元素不一定有序。

11. Top K 方向选反

前 K 大不是使用大堆，而是使用大小为 K 的小堆；前 K 小不是使用小堆，而是使用大小为 K 的大堆。

12. 忽略 K 的边界

至少要处理：

K <= 0
K > n
n <= 0
array == NULL
result == NULL

13. 忘记释放内存

树节点通过 malloc 申请，就要通过 free 释放；栈和队列中的数组也要在使用结束后释放。

十八、完整可运行代码

下面的代码把本文最主要的内容放在一起：

二叉树的创建和释放；
三种遍历的递归版本；
三种遍历的迭代版本；
层序遍历；
大堆建堆；
堆排序；
前 K 大。

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

typedef struct Node
{
char data;
struct Node* left;
struct Node* right;
} Node;

typedef struct Stack
{
Node** data;
int size;
int capacity;
} Stack;

typedef struct Queue
{
Node** data;
int front;
int size;
int capacity;
} Queue;

Node* create_node(char data)
{
Node* node = (Node*)malloc(sizeof(Node));
if (node == NULL)
{
printf("malloc failed\\n");
exit(1);
}

node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}

Node* create_tree(void)
{
Node* a = create_node('A');
Node* b = create_node('B');
Node* c = create_node('C');
Node* d = create_node('D');
Node* e = create_node('E');
Node* f = create_node('F');

a->left = b;
a->right = c;
b->left = d;
b->right = e;
c->right = f;

return a;
}

void destroy_tree(Node* root)
{
if (root == NULL)
{
return;
}

destroy_tree(root->left);
destroy_tree(root->right);
free(root);
}

void preorder(Node* root)
{
if (root == NULL)
{
return;
}

printf("%c ", root->data);
preorder(root->left);
preorder(root->right);
}

void inorder(Node* root)
{
if (root == NULL)
{
return;
}

inorder(root->left);
printf("%c ", root->data);
inorder(root->right);
}

void postorder(Node* root)
{
if (root == NULL)
{
return;
}

postorder(root->left);
postorder(root->right);
printf("%c ", root->data);
}

void stack_init(Stack* stack)
{
stack->capacity = 8;
stack->size = 0;
stack->data = (Node**)malloc(
sizeof(Node*) * stack->capacity);

if (stack->data == NULL)
{
printf("malloc failed\\n");
exit(1);
}
}

void stack_push(Stack* stack, Node* node)
{
if (stack->size == stack->capacity)
{
stack->capacity *= 2;
Node** new_data = (Node**)realloc(
stack->data,
sizeof(Node*) * stack->capacity);

if (new_data == NULL)
{
free(stack->data);
printf("realloc failed\\n");
exit(1);
}

stack->data = new_data;
}

stack->data[stack->size++] = node;
}

Node* stack_pop(Stack* stack)
{
if (stack->size == 0)
{
return NULL;
}

return stack->data[—stack->size];
}

Node* stack_top(Stack* stack)
{
if (stack->size == 0)
{
return NULL;
}

return stack->data[stack->size – 1];
}

int stack_empty(Stack* stack)
{
return stack->size == 0;
}

void stack_destroy(Stack* stack)
{
free(stack->data);
stack->data = NULL;
stack->size = 0;
stack->capacity = 0;
}

void preorder_loop(Node* root)
{
if (root == NULL)
{
return;
}

Stack stack;
stack_init(&stack);
stack_push(&stack, root);

while (!stack_empty(&stack))
{
Node* cur = stack_pop(&stack);
printf("%c ", cur->data);

if (cur->right != NULL)
{
stack_push(&stack, cur->right);
}

if (cur->left != NULL)
{
stack_push(&stack, cur->left);
}
}

stack_destroy(&stack);
}

void inorder_loop(Node* root)
{
Stack stack;
stack_init(&stack);

Node* cur = root;

while (cur != NULL || !stack_empty(&stack))
{
while (cur != NULL)
{
stack_push(&stack, cur);
cur = cur->left;
}

cur = stack_pop(&stack);
printf("%c ", cur->data);
cur = cur->right;
}

stack_destroy(&stack);
}

void postorder_loop(Node* root)
{
Stack stack;
stack_init(&stack);

Node* cur = root;
Node* last = NULL;

while (cur != NULL || !stack_empty(&stack))
{
while (cur != NULL)
{
stack_push(&stack, cur);
cur = cur->left;
}

Node* top = stack_top(&stack);

if (top->right != NULL && top->right != last)
{
cur = top->right;
}
else
{
printf("%c ", top->data);
last = stack_pop(&stack);
}
}

stack_destroy(&stack);
}

void queue_init(Queue* queue)
{
queue->capacity = 8;
queue->front = 0;
queue->size = 0;
queue->data = (Node**)malloc(
sizeof(Node*) * queue->capacity);

if (queue->data == NULL)
{
printf("malloc failed\\n");
exit(1);
}
}

int queue_empty(Queue* queue)
{
return queue->size == 0;
}

void queue_push(Queue* queue, Node* node)
{
if (queue->size == queue->capacity)
{
int new_capacity = queue->capacity * 2;
Node** new_data = (Node**)malloc(
sizeof(Node*) * new_capacity);

if (new_data == NULL)
{
printf("malloc failed\\n");
exit(1);
}

for (int i = 0; i < queue->size; i++)
{
int index = (queue->front + i)
% queue->capacity;
new_data[i] = queue->data[index];
}

free(queue->data);
queue->data = new_data;
queue->capacity = new_capacity;
queue->front = 0;
}

int tail = (queue->front + queue->size)
% queue->capacity;
queue->data[tail] = node;
queue->size++;
}

Node* queue_pop(Queue* queue)
{
if (queue_empty(queue))
{
return NULL;
}

Node* node = queue->data[queue->front];
queue->front = (queue->front + 1)
% queue->capacity;
queue->size—;
return node;
}