# 堆排序

# 一、堆的知识点笔记

# 1. 堆的基本概念

堆是一种特殊的完全二叉树，通常用数组顺序存储。

堆有两个核心要求：

1. 结构上必须是完全二叉树。
2. 数值上要满足堆的大小关系。

大根堆要求：

父节点 >= 子节点

小根堆要求：

父节点 <= 子节点

大根堆的堆顶是最大值。
小根堆的堆顶是最小值。

---

# 2. 堆的数组下标关系

如果数组下标从 1 开始：

父节点 i
左孩子 2i
右孩子 2i + 1

如果数组下标从 0 开始：

父节点 (i - 1) / 2
左孩子 2i + 1
右孩子 2i + 2

考试中很多堆题默认下标从 1 开始。

---

# 3. 堆的插入操作

堆插入新元素时，不能指定位置插入。

标准流程是：

1. 新元素先放到堆的末尾
2. 和父节点比较
3. 如果不满足堆的性质，就向上调整

以大根堆为例：

如果新元素 > 父节点，就交换
如果新元素 <= 父节点，就停止

以小根堆为例：

如果新元素 < 父节点，就交换
如果新元素 >= 父节点，就停止

插入操作的调整方向是​向上调整。

时间复杂度：

O(log n)

易错点：

最后一次判断“不需要交换”的比较也要算入关键字比较次数。

---

# 4. 堆的删除操作

堆最常见的删除操作是删除堆顶元素。

大根堆删除堆顶，就是删除最大值。
小根堆删除堆顶，就是删除最小值。

标准流程是：

1. 删除堆顶元素
2. 用最后一个元素补到堆顶
3. 从堆顶开始向下调整

为什么用最后一个元素补堆顶？

因为堆必须保持完全二叉树结构。
最后一个元素是最右下角的叶子结点，删除它不会破坏完全二叉树。

如果用堆顶的子结点补上去，中间会留下空洞，还要继续补空位，过程复杂，也不符合标准堆删除操作。

---

# 5. 删除后的向下调整

以大根堆为例，向下调整时：

1. 先比较左右孩子，选较大的孩子
2. 再让当前元素和较大的孩子比较
3. 如果当前元素小，就交换
4. 继续向下检查

以小根堆为例，向下调整时：

1. 先比较左右孩子，选较小的孩子
2. 再让当前元素和较小的孩子比较
3. 如果当前元素大，就交换
4. 继续向下检查

删除操作的调整方向通常是​向下调整。

时间复杂度：

O(log n)

易错点：

向下调整中，最后一次判断“不需要交换”的比较也要算入关键字比较次数。

---

# 6. 大根堆能不能删除特定元素

可以删除，但不擅长。

如果只知道元素值，不知道位置，需要先查找该元素。

查找：O(n)
调整：O(log n)
整体：O(n)

如果已经知道该元素的位置，就可以：

1. 用最后一个元素替换该位置
2. 根据情况向上或向下调整

如果替换后的元素比父节点大，大根堆中要向上调整。
如果替换后的元素比孩子小，大根堆中要向下调整。

所以准确说：

堆不是不能删除特定元素，而是不擅长快速查找并删除特定元素。

---

# 7. 堆是否支持插入到特定位置

一般不支持。

堆的插入位置由完全二叉树结构决定，新元素必须先插入到最后一个位置。

堆不是按位置组织数据的，而是按优先级组织数据的。

所以堆关心的是：

堆顶最大或最小
父子之间满足大小关系
整体保持完全二叉树

它不关心某个元素必须放在哪个具体位置。

---

# 8. 建堆操作

建堆不是从第一个元素开始调，而是从最后一个非叶子结点开始调。

如果有 n 个元素，最后一个非叶子结点是：

n / 2

从这个位置开始，依次向前调整：

n/2, n/2 - 1, ..., 1

建堆的时间复杂度是：

O(n)

注意：

如果一个一个插入来建堆，复杂度是：

O(nlog n)

但堆排序中的建初始堆是自底向上调整，所以是：

O(n)

---

# 9. 堆排序

堆排序的基本流程是：

1. 建初始堆
2. 输出堆顶元素
3. 用最后一个元素补堆顶
4. 重新调整堆
5. 重复直到排序完成

如果要从小到大排序，通常使用大根堆。
每次把最大值放到数组末尾。

堆排序时间复杂度：

最好：O(nlog n)
平均：O(nlog n)
最坏：O(nlog n)

空间复杂度：

O(1)

稳定性：

不稳定

原因是堆排序中会发生远距离交换，相同关键字的相对顺序可能被改变。

---

# 10. 堆与 Top-K 问题

堆非常适合处理海量数据中的前 k 个数问题。

如果要选最大的 k 个数，用小根堆。

原因是：

小根堆堆顶是当前 k 个候选数中最小的数。
如果新数比堆顶还小，就没资格进入最大 k 个数。
如果新数比堆顶大，就替换堆顶，然后调整小根堆。

如果要选最小的 k 个数，用大根堆。

原因是：

大根堆堆顶是当前 k 个候选数中最大的数。
如果新数比堆顶还大，就没资格进入最小 k 个数。
如果新数比堆顶小，就替换堆顶，然后调整大根堆。

记忆：

选最大 k 个数，用小根堆
选最小 k 个数，用大根堆

堆顶保存的是当前结果中最容易被淘汰的那个元素。

---

# 二、做题整理

# 第 2 题

题目文字版

简单选择排序算法的比较次数和移动次数分别为（ ）。

A. O(n)，O(log₂n)​
B. O(log₂n)，O(n²)​
C. O(n²)，O(n)​
D. O(nlog₂n)，O(n)

答案

C

[!NOTE]
解析

简单选择排序每一趟都要在未排序部分中找最小值。

比较次数为：

(n - 1) + (n - 2) + ... + 1 = O(n²)

但是每一趟最多只交换一次，所以移动次数是：

O(n)

所以答案是：

比较次数 O(n²)，移动次数 O(n)

---

# 第 5 题

题目文字版

在含有 n​ 个元素的小根堆中，下标从 1 开始，关键字最大的元素可能存储在（ ）位置。

A. n/2​
B. n/2 + 2​
C. 1​
D. n/2 - 1

答案

B

[!NOTE]
解析

小根堆满足：

父节点 <= 子节点

所以堆顶一定是最小值。

关键字最大的元素一般只能出现在叶子结点中。

下标从 1 开始时：

1 到 n/2 是非叶子结点
n/2 + 1 到 n 是叶子结点

四个选项中，只有 n/2 + 2 属于叶子结点区域。

所以选：

B

---

# 第 7 题

题目文字版

构建 n​ 个记录的初始堆，其时间复杂度为（ ）；对 n 个记录进行堆排序，最坏情况下其时间复杂度为（ ）。

A. O(n)​
B. O(n²)​
C. O(log₂n)​
D. O(nlog₂n)

答案

A，D

[!NOTE]
解析

构建初始堆不是一个一个插入，而是从最后一个非叶子结点开始向前调整。

所以建堆时间复杂度是：

O(n)

堆排序时，建堆之后要进行大约 n - 1 次删除堆顶和向下调整。

每次调整最多走堆的高度：

O(log₂n)

所以堆排序最坏时间复杂度是：

O(nlog₂n)

---

# 第 9 题

题目文字版

对由相同的 n 个整数构成的二叉排序树和小根堆，下列说法中不正确的是（ ）。

A. 二叉排序树的高度大于或等于小根堆的高度。
B. 对二叉排序树进行中序遍历可以得到从小到大的序列。
C. 从小根堆的根结点到任意叶结点的路径构成从小到大的序列。
D. 对小根堆进行层次遍历可以得到从小到大的序列。

答案

D

[!NOTE]
解析

A 正确。
小根堆是完全二叉树，结构最紧凑，所以高度较低。普通二叉排序树可能不平衡，高度大于或等于小根堆高度。

B 正确。
二叉排序树的中序遍历结果是递增序列。

C 正确。
小根堆满足：

父节点 <= 子节点

所以从根结点到叶结点的路径上，关键字是非递减的。

D 错误。
小根堆只保证父子之间有序，不保证层次遍历整体有序。

所以选：

D

---

# 第 11 题

题目文字版

对关键字序列：

23, 17, 72, 60, 25, 8, 68, 71, 52

进行堆排序，输出两个最小关键字后的剩余堆是（ ）。

A. {23, 72, 60, 25, 68, 71, 52}​
B. {23, 25, 52, 60, 71, 72, 68}​
C. {71, 25, 23, 52, 60, 72, 68}​
D. {23, 25, 68, 52, 60, 72, 71}

答案

D

[!NOTE]
解析

要输出两个最小关键字，所以要建立小根堆。

原序列：

23, 17, 72, 60, 25, 8, 68, 71, 52

建成小根堆后：

8, 17, 23, 52, 25, 72, 68, 71, 60

第一次输出最小值 8。

用最后一个元素 60 补到堆顶：

60, 17, 23, 52, 25, 72, 68, 71

向下调整后：

17, 25, 23, 52, 60, 72, 68, 71

第二次输出最小值 17。

用最后一个元素 71 补到堆顶：

71, 25, 23, 52, 60, 72, 68

向下调整：

23, 25, 71, 52, 60, 72, 68

继续调整：

23, 25, 68, 52, 60, 72, 71

所以最终剩余堆是：

23, 25, 68, 52, 60, 72, 71

选：

D

注意，B 虽然也是一个合法小根堆，但它不是按照题目给定序列执行堆排序过程得到的结果。

---

# 第 16 题

题目文字版

已知序列：

25, 13, 10, 12, 9

是大根堆，在序列尾部插入新元素 18，再将其调整为大根堆，调整过程中元素之间进行的比较次数是（ ）。

A. 1​
B. 2​
C. 4
D. 图片中被笔迹遮挡，未辨清

答案

B

[!NOTE]
解析

原大根堆：

25, 13, 10, 12, 9

插入 18 后：

25, 13, 10, 12, 9, 18

​18​ 的父节点是 10。

第一次比较：

18 和 10 比

因为：

18 > 10

所以交换：

25, 13, 18, 12, 9, 10

现在 18​ 的父节点是 25。

第二次比较：

18 和 25 比

因为：

18 < 25

满足大根堆，停止。

所以比较次数是：

2 次

这题容易漏掉最后一次“不需要交换”的比较。

---

# 第 17 题

题目文字版

已知小根堆为：

8, 15, 10, 21, 34, 16, 12

删除关键字 8 之后需重建堆，在此过程中，关键字之间的比较次数是（ ）。

A. 1​
B. 2​
C. 3​
D. 4

答案

C

[!NOTE]
解析

删除堆顶 8​，用最后一个元素 12 补到堆顶：

12, 15, 10, 21, 34, 16

开始向下调整。

第一次比较左右孩子：

15 和 10 比

较小的是 10。

第二次比较当前元素和较小孩子：

12 和 10 比

因为：

12 > 10

所以交换：

10, 15, 12, 21, 34, 16

现在 12​ 还有一个孩子 16。

第三次比较：

12 和 16 比

因为：

12 < 16

满足小根堆，停止。

所以比较次数是：

3 次

选：

C

---

# 第 18 题

题目文字版

将序列：

6, 1, 5, 9, 8, 4, 7

建成大根堆时，正确的序列变化过程是（ ）。

A. 6,1,7,9,8,4,5 → 6,9,7,1,8,4,5 → 9,6,7,1,8,4,5 → 9,8,7,1,6,4,5

B. 6,9,5,1,8,4,7 → 6,9,7,1,8,4,5 → 9,6,7,1,8,4,5 → 9,8,7,1,6,4,5

C. 6,9,5,1,8,4,7 → 9,6,5,1,8,4,7 → 9,6,7,1,8,4,5 → 9,8,7,1,6,4,5

D. 6,1,7,9,8,4,5 → 7,1,6,9,8,4,5 → 7,9,6,1,8,4,5 → 9,7,6,1,8,4,5 → ...

答案

A

[!NOTE]
解析

原序列：

6, 1, 5, 9, 8, 4, 7

一共有 7 个元素，最后一个非叶子结点是：

7 / 2 = 3

所以从第 3 个位置开始向前调整。

第一步，调整 5。

​5​ 的孩子是 4​ 和 7​，较大的是 7。

交换后：

6, 1, 7, 9, 8, 4, 5

第二步，调整 1。

​1​ 的孩子是 9​ 和 8​，较大的是 9。

交换后：

6, 9, 7, 1, 8, 4, 5

第三步，调整 6。

​6​ 的孩子是 9​ 和 7​，较大的是 9。

交换后：

9, 6, 7, 1, 8, 4, 5

此时 6​ 下沉到第 2 个位置，它还有孩子 1​ 和 8。

较大的是 8，继续交换：

9, 8, 7, 1, 6, 4, 5

所以正确变化过程是：

6,1,7,9,8,4,5
6,9,7,1,8,4,5
9,6,7,1,8,4,5
9,8,7,1,6,4,5

选：

A

---

# 三、今天最重要的易错点总结

1. 堆插入时，新元素必须先放到末尾，然后向上调整。
2. 堆删除堆顶时，必须用最后一个元素补到堆顶，然后向下调整。
3. 建堆从最后一个非叶子结点开始，不是从根节点开始。
4. 大根堆向下调整时，优先选较大的孩子。
5. 小根堆向下调整时，优先选较小的孩子。
6. 比较次数题中，最后一次判断“不交换”的比较也要算。
7. 合法堆不唯一，但题目问算法过程时，必须按给定过程一步步调整。
8. 选最大 k 个数用小根堆，选最小 k 个数用大根堆。

‍