8.5 练习¶
8.5.1 知识巩固¶
1. 数字 10 入堆后怎样调整¶
数组 [9, 7, 8, 3, 5] 表示一个大顶堆。现在将数字 10 入堆。
- 先把 10 添加到数组末尾，它的父节点值是多少？
- 从新节点开始向上堆化，写出每次交换后的数组。
- 最终的堆顶元素是什么？一共交换了几次？
参考答案
-
10 添加后的索引为 5，其父节点索引为 \(\lfloor(5-1)/2\rfloor=2\)，父节点值为 8。
-
10 大于 8，第一次交换后为
[9, 7, 10, 3, 5, 8]； 10 又大于父节点 9，第二次交换后为[10, 7, 9, 3, 5, 8]。 此时 10 已到达根节点，堆化结束。 -
最终堆顶为 10，共交换 2 次。
2. 检查小顶堆的父子关系¶
数组 [1, 4, 3, 7, 6, 2] 表示一棵完全二叉树。小顶堆要求每个父节点都不大于它的孩子。
对索引 \(i\)，左、右孩子索引分别为 \(2i+1\) 和 \(2i+2\)。
- 索引 2 的孩子索引和值分别是什么？
- 索引 2 处的节点值为 3，它与孩子节点之间是否违反小顶堆规则？如果违反，应交换哪两个元素？
- 根据第 2 问的判断：若违反规则，写出交换后的数组；若不违反，说明无须交换。最后检查其余父子关系。
参考答案
-
索引 2 的左孩子索引是 5、值为 2；右孩子索引是 6，但数组长度为 6，因此右孩子不存在。
-
父节点值 3 大于孩子值 2，违反小顶堆规则，应交换索引 2 和索引 5 的元素。
-
交换后得到
[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\) 的小顶堆完成。
解题提示
- 第 k 大元素是最大的 k 个数中最小的那个
- 每个数先入小顶堆，大小超过 k 时弹出最小值
- 遍历结束时堆中保留最大的 k 个数，堆顶就是答案
说明： 链接中的题解讲解了快速排序和快速选择，没有使用堆；本练习请按照正文 8.3 节使用大小不超过 k 的小顶堆完成