跳转至
纸质书已发行，详情请见这里

# 8.5 练习

## 8.5.1 知识巩固

### 1. 数字 10 入堆后怎样调整

数组 `[9, 7, 8, 3, 5]` 表示一个大顶堆。现在将数字 10 入堆。

1. 先把 10 添加到数组末尾，它的父节点值是多少？
2. 从新节点开始向上堆化，写出每次交换后的数组。
3. 最终的堆顶元素是什么？一共交换了几次？

参考答案

1. 10 添加后的索引为 5，其父节点索引为 \(\lfloor(5-1)/2\rfloor=2\)，父节点值为 8。

2. 10 大于 8，第一次交换后为 `[9, 7, 10, 3, 5, 8]`； 10 又大于父节点 9，第二次交换后为 `[10, 7, 9, 3, 5, 8]`。 此时 10 已到达根节点，堆化结束。

3. 最终堆顶为 10，共交换 2 次。

### 2. 检查小顶堆的父子关系

数组 `[1, 4, 3, 7, 6, 2]` 表示一棵完全二叉树。小顶堆要求每个父节点都不大于它的孩子。 对索引 \(i\)，左、右孩子索引分别为 \(2i+1\) 和 \(2i+2\)。

1. 索引 2 的孩子索引和值分别是什么？
2. 索引 2 处的节点值为 3，它与孩子节点之间是否违反小顶堆规则？如果违反，应交换哪两个元素？
3. 根据第 2 问的判断：若违反规则，写出交换后的数组；若不违反，说明无须交换。最后检查其余父子关系。

参考答案

1. 索引 2 的左孩子索引是 5、值为 2；右孩子索引是 6，但数组长度为 6，因此右孩子不存在。

2. 父节点值 3 大于孩子值 2，违反小顶堆规则，应交换索引 2 和索引 5 的元素。

3. 交换后得到 `[1, 4, 2, 7, 6, 3]`。逐一检查： `1 ≤ 4`、`1 ≤ 2`；`4 ≤ 7`、`4 ≤ 6`；`2 ≤ 3`。 所有父节点都不大于自己的孩子，因此现在满足小顶堆规则。

### 3. 用小顶堆保留最大的三个数

要从数据流 `[4, 1, 7, 3, 8]` 中保留最大的 3 个数，可以维护一个大小不超过 3 的小顶堆。

先把前 3 个数依次放入小顶堆。堆满后，每读入一个新数： 如果它大于堆顶，就删除堆顶并放入新数；否则堆保持不变。

请写出每次读入数字后堆中保留的数字和堆顶。 只需把保留的数字写成集合，不要求写出它们在堆数组中的排列。

参考答案

每次读入数字后的结果如下：

读入数字 | 保留的数字 | 堆顶
--- | --- | ---
4 | `{4}` | 4
1 | `{1, 4}` | 1
7 | `{1, 4, 7}` | 1
3 | `{3, 4, 7}` | 3
8 | `{4, 7, 8}` | 4

堆满后，堆顶是当前保留数字中最小的一个。只有新数字大于堆顶时， 才用新数字替换堆顶。最终保留的 `{4, 7, 8}` 正是最大的 3 个数。

## 8.5.2 编程练习

### 1. 寻找数组中的第 k 大元素

给定整数数组 `nums` 和整数 \(k\)，其中 \(1 \le k \le n\)，\(n\) 是数组长度。把数组按从大到小排列后，请返回第 \(k\) 个位置上的元素。

重复元素需要分别计数。例如，`[5, 5, 2]` 的第 2 大元素仍是 5。请使用一个大小不超过 \(k\) 的小顶堆完成。

解题提示

1. 第 k 大元素是最大的 k 个数中最小的那个
2. 每个数先入小顶堆，大小超过 k 时弹出最小值
3. 遍历结束时堆中保留最大的 k 个数，堆顶就是答案

LeetCode 题目解析

> 说明： 链接中的题解讲解了快速排序和快速选择，没有使用堆；本练习请按照正文 8.3 节使用大小不超过 k 的小顶堆完成

##### 欢迎在评论区留下你的见解、问题或建议