练习

知识巩固

数字 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 次。

检查小顶堆的父子关系

数组 [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。 所有父节点都不大于自己的孩子，因此现在满足小顶堆规则。

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

要从数据流 [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 个数。

编程练习

寻找数组中的第 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 的小顶堆完成