8.3 Top-k 问题¶
Question
给定一个长度为 \(n\) 的无序数组 nums ,请返回数组中最大的 \(k\) 个元素。
对于该问题,我们先介绍两种思路比较直接的解法,再介绍效率更高的堆解法。
8.3.1 方法一:遍历选择¶
我们可以进行图 8-6 所示的 \(k\) 轮遍历,分别在每轮中提取第 \(1\)、\(2\)、\(\dots\)、\(k\) 大的元素,时间复杂度为 \(O(nk)\) 。
此方法只适用于 \(k \ll n\) 的情况,因为当 \(k\) 与 \(n\) 比较接近时,其时间复杂度趋向于 \(O(n^2)\) ,非常耗时。
图 8-6 遍历寻找最大的 k 个元素
图解 8-6:遍历选择 Top-k
每轮从未选元素中找出最大值,选出的元素不再参加后续轮次。
本例输入有 5 个元素,k=3。图自上而下共四行,第一行是初始数组,其下是三轮选择后的状态;左侧为待选区,右侧蓝框为已选区。
每次把新选出的元素放到右侧已选区的左端,因此画面从左到右的排列与提取的时间顺序相反;这只是放置位置,不表示又做了一次排序。
向下的灰色粗箭头表示轮次推进,曲线细箭头标出每轮提取的最大值。下表的左侧未选候选、右侧已选区两列来自图上区域;“累计提取顺序”由各轮选出的值按时间先后汇总,不是图中另画的一排数组。
每轮只在左侧未选元素中比较。第二轮选出的 6 放在 7 左边,第三轮选出的 3 再放到 6 左边;已选元素保持在右侧。
| 阶段 | 左侧未选候选 | 右侧已选区,从左到右 | 累计提取顺序 |
|---|---|---|---|
| 初始 | [1, 7, 6, 3, 2] | 空 | 空 |
| 第一轮:找到第 1 大元素 7 | [1, 6, 3, 2] | [7] | [7] |
| 第二轮:找到第 2 大元素 6 | [1, 3, 2] | [6, 7] | [7, 6] |
| 第三轮:找到第 3 大元素 3 | [1, 2] | [3, 6, 7] | [7, 6, 3] |
执行 k 轮线性扫描可找齐最大的 k 个元素,总时间复杂度为 O(nk)。
Tip
当 \(k = n\) 时,我们可以得到完整的有序序列,此时等价于“选择排序”算法。
8.3.2 方法二:排序¶
如图 8-7 所示,我们可以先对数组 nums 进行排序,再返回最右边的 \(k\) 个元素,时间复杂度为 \(O(n \log n)\) 。
显然,该方法“超额”完成任务了,因为我们只需找出最大的 \(k\) 个元素即可,而不需要排序其他元素。
图 8-7 排序寻找最大的 k 个元素
图解 8-7:方法二(排序):先升序排序,再返回最右 k 个元素
先对整个数组升序排序,再截取末尾的 k 个元素。
本例 k=3,图自上而下共三行:输入、排序后的数组、截取结果。第一行是 nums = [1, 7, 6, 3, 2]。
第一个向下箭头标注“对数组进行排序”,第二行变为 [1, 2, 3, 6, 7];最右侧三个元素 3、6、7 用蓝色边框和下方花括号标出。
第二个向下箭头标注“返回最右 k 个元素”,第三行只留下 [3, 6, 7],较小的 1 和 2 被舍弃。升序数组右侧元素更大,所以取末尾 k 项即可。
采用 O(n log n) 的排序算法时,总时间为 O(n log n);这种方法也对无需返回的其余元素做了排序。
8.3.3 方法三:堆¶
我们可以基于堆更加高效地解决 Top-k 问题,流程如图 8-8 所示。
- 初始化一个小顶堆,其堆顶元素最小。
- 先将数组的前 \(k\) 个元素依次入堆。
- 从第 \(k + 1\) 个元素开始,若当前元素大于堆顶元素,则将堆顶元素出堆,并将当前元素入堆。
- 遍历完成后,堆中保存的就是最大的 \(k\) 个元素。
图 8-8 基于堆寻找最大的 k 个元素
图解 8-8:用小顶堆寻找 Top-k
维护至多 k 个候选,用其中最小值与后续元素比较,逐步保留最大的 k 个值。
本例 k=3,输入数组及其索引见下表。指针 i 表示输入索引;heap 是小顶堆的层序数组,堆索引 0 存放最小候选,左、右子节点分别在堆索引 1、2(若存在)。输入索引表示元素来源,堆索引表示当前存储位置。
先把前 k 个输入依次入堆,随后逐个比较:当前值大于堆顶时,先弹出堆顶再加入当前值,否则跳过。表格按步号命名;比较或跳过时堆未改变,按表名引用相应的候选与来源索引。
堆顶是候选中最小的值。遇到更大的新值时,用它替换堆顶,仍能保留已处理输入中最大的 k 个值。查看堆顶用 O(1) 时间,入堆或出堆调整用 O(log k) 时间。
| 输入索引 | 值 |
|---|---|
| 0 | 1 |
| 1 | 7 |
| 2 | 6 |
| 3 | 3 |
| 4 | 2 |
将1加入空堆
指针 i=0,读取值 1 加入空堆。当前只有 1 个候选 [1],堆顶为 1。
第 1 步候选:加入 1 后 堆数组索引 值 来自输入索引 0 1 0 将7入堆
指针 i=1,读取值 7 入堆,挂在堆索引 1。父节点 1 小于 7,无须上浮;当前 2 个候选为 [1, 7],堆顶为 1。
第 2 步候选:加入 7 后 堆数组索引 值 来自输入索引 0 1 0 1 7 1 将6入堆,初始候选齐备
指针 i=2,读取值 6 入堆,挂在堆索引 2。当前 3 个候选为 [1, 7, 6],堆顶为 1;前 k=3 个输入已全部入堆,接下来比较后续元素。
第 3 步候选:初始三项齐备 堆数组索引 值 来自输入索引 0 1 0 1 7 1 2 6 2 比较当前3与堆顶1
指针 i=3,当前值 3 大于最小候选 1,准备替换。本步仅比较,尚未弹出或加入元素;3 个候选仍是 [1, 7, 6],堆顶为 1。候选与来源索引见“第 3 步候选:初始三项齐备”表。
弹出旧堆顶1
指针仍为 i=3,先弹出旧堆顶 1,剩余元素调整为 [6, 7],堆顶暂为 6。当前只有 k−1=2 个候选,值 3 尚待入堆;这是替换的中间状态,没有漏掉结果,也尚未完成这一轮。
第 5 步候选:弹出 1 后的中间态 堆数组索引 值 来自输入索引 0 6 2 1 7 1 将3入堆
指针仍为 i=3,将值 3 入堆并上浮至根,恢复 k=3 个候选 [3, 7, 6],新堆顶为 3。这三个候选是前 4 个输入中的最大三个值。
第 6 步候选:加入 3 后 堆数组索引 值 来自输入索引 0 3 3 1 7 1 2 6 2 比较当前2与堆顶3
指针 i=4,当前值 2 小于堆顶 3,不满足替换条件。本步仅比较,3 个候选仍为 [3, 7, 6]。候选与来源索引见“第 6 步候选:加入 3 后”表。
跳过2
指针 i=4,由于 2 小于堆顶 3,跳过它,不做出堆或入堆。3 个候选仍为 [3, 7, 6],堆顶为 3;全部输入已处理。候选与来源索引见“第 6 步候选:加入 3 后”表。
返回三个候选
遍历结束,无当前指针,直接返回小顶堆 [3, 7, 6]。三个候选的输入来源见下表;堆顶为 3,但左右子节点 7 和 6 不必升序,这里没有再做排序。
第 9 步最终返回的候选与来源 堆数组索引 值 来自输入索引 0 3 3 1 7 1 2 6 2
堆内至多保留 k 个候选,空间复杂度为 O(k),总时间复杂度为 O(n log k)。
示例代码如下:
def top_k_heap(nums: list[int], k: int) -> list[int]:
"""基于堆查找数组中最大的 k 个元素"""
# 初始化小顶堆
heap = []
# 将数组的前 k 个元素入堆
for i in range(k):
heapq.heappush(heap, nums[i])
# 从第 k+1 个元素开始,保持堆的长度为 k
for i in range(k, len(nums)):
# 若当前元素大于堆顶元素,则将堆顶元素出堆、当前元素入堆
if nums[i] > heap[0]:
heapq.heappop(heap)
heapq.heappush(heap, nums[i])
return heap
/* 基于堆查找数组中最大的 k 个元素 */
priority_queue<int, vector<int>, greater<int>> topKHeap(vector<int> &nums, int k) {
// 初始化小顶堆
priority_queue<int, vector<int>, greater<int>> heap;
// 将数组的前 k 个元素入堆
for (int i = 0; i < k; i++) {
heap.push(nums[i]);
}
// 从第 k+1 个元素开始,保持堆的长度为 k
for (int i = k; i < nums.size(); i++) {
// 若当前元素大于堆顶元素,则将堆顶元素出堆、当前元素入堆
if (nums[i] > heap.top()) {
heap.pop();
heap.push(nums[i]);
}
}
return heap;
}
/* 基于堆查找数组中最大的 k 个元素 */
Queue<Integer> topKHeap(int[] nums, int k) {
// 初始化小顶堆
Queue<Integer> heap = new PriorityQueue<Integer>();
// 将数组的前 k 个元素入堆
for (int i = 0; i < k; i++) {
heap.offer(nums[i]);
}
// 从第 k+1 个元素开始,保持堆的长度为 k
for (int i = k; i < nums.length; i++) {
// 若当前元素大于堆顶元素,则将堆顶元素出堆、当前元素入堆
if (nums[i] > heap.peek()) {
heap.poll();
heap.offer(nums[i]);
}
}
return heap;
}
/* 基于堆查找数组中最大的 k 个元素 */
PriorityQueue<int, int> TopKHeap(int[] nums, int k) {
// 初始化小顶堆
PriorityQueue<int, int> heap = new();
// 将数组的前 k 个元素入堆
for (int i = 0; i < k; i++) {
heap.Enqueue(nums[i], nums[i]);
}
// 从第 k+1 个元素开始,保持堆的长度为 k
for (int i = k; i < nums.Length; i++) {
// 若当前元素大于堆顶元素,则将堆顶元素出堆、当前元素入堆
if (nums[i] > heap.Peek()) {
heap.Dequeue();
heap.Enqueue(nums[i], nums[i]);
}
}
return heap;
}
/* 基于堆查找数组中最大的 k 个元素 */
func topKHeap(nums []int, k int) *minHeap {
// 初始化小顶堆
h := &minHeap{}
heap.Init(h)
// 将数组的前 k 个元素入堆
for i := 0; i < k; i++ {
heap.Push(h, nums[i])
}
// 从第 k+1 个元素开始,保持堆的长度为 k
for i := k; i < len(nums); i++ {
// 若当前元素大于堆顶元素,则将堆顶元素出堆、当前元素入堆
if nums[i] > h.Top().(int) {
heap.Pop(h)
heap.Push(h, nums[i])
}
}
return h
}
/* 基于堆查找数组中最大的 k 个元素 */
func topKHeap(nums: [Int], k: Int) -> [Int] {
// 初始化一个小顶堆,并将前 k 个元素建堆
var heap = Heap(nums.prefix(k))
// 从第 k+1 个元素开始,保持堆的长度为 k
for i in nums.indices.dropFirst(k) {
// 若当前元素大于堆顶元素,则将堆顶元素出堆、当前元素入堆
if nums[i] > heap.min()! {
_ = heap.removeMin()
heap.insert(nums[i])
}
}
return heap.unordered
}
/* 元素入堆 */
function pushMinHeap(maxHeap, val) {
// 元素取反
maxHeap.push(-val);
}
/* 元素出堆 */
function popMinHeap(maxHeap) {
// 元素取反
return -maxHeap.pop();
}
/* 访问堆顶元素 */
function peekMinHeap(maxHeap) {
// 元素取反
return -maxHeap.peek();
}
/* 取出堆中元素 */
function getMinHeap(maxHeap) {
// 元素取反
return maxHeap.getMaxHeap().map((num) => -num);
}
/* 基于堆查找数组中最大的 k 个元素 */
function topKHeap(nums, k) {
// 初始化小顶堆
// 请注意:我们将堆中所有元素取反,从而用大顶堆来模拟小顶堆
const maxHeap = new MaxHeap([]);
// 将数组的前 k 个元素入堆
for (let i = 0; i < k; i++) {
pushMinHeap(maxHeap, nums[i]);
}
// 从第 k+1 个元素开始,保持堆的长度为 k
for (let i = k; i < nums.length; i++) {
// 若当前元素大于堆顶元素,则将堆顶元素出堆、当前元素入堆
if (nums[i] > peekMinHeap(maxHeap)) {
popMinHeap(maxHeap);
pushMinHeap(maxHeap, nums[i]);
}
}
// 返回堆中元素
return getMinHeap(maxHeap);
}
/* 元素入堆 */
function pushMinHeap(maxHeap: MaxHeap, val: number): void {
// 元素取反
maxHeap.push(-val);
}
/* 元素出堆 */
function popMinHeap(maxHeap: MaxHeap): number {
// 元素取反
return -maxHeap.pop();
}
/* 访问堆顶元素 */
function peekMinHeap(maxHeap: MaxHeap): number {
// 元素取反
return -maxHeap.peek();
}
/* 取出堆中元素 */
function getMinHeap(maxHeap: MaxHeap): number[] {
// 元素取反
return maxHeap.getMaxHeap().map((num: number) => -num);
}
/* 基于堆查找数组中最大的 k 个元素 */
function topKHeap(nums: number[], k: number): number[] {
// 初始化小顶堆
// 请注意:我们将堆中所有元素取反,从而用大顶堆来模拟小顶堆
const maxHeap = new MaxHeap([]);
// 将数组的前 k 个元素入堆
for (let i = 0; i < k; i++) {
pushMinHeap(maxHeap, nums[i]);
}
// 从第 k+1 个元素开始,保持堆的长度为 k
for (let i = k; i < nums.length; i++) {
// 若当前元素大于堆顶元素,则将堆顶元素出堆、当前元素入堆
if (nums[i] > peekMinHeap(maxHeap)) {
popMinHeap(maxHeap);
pushMinHeap(maxHeap, nums[i]);
}
}
// 返回堆中元素
return getMinHeap(maxHeap);
}
/* 基于堆查找数组中最大的 k 个元素 */
MinHeap topKHeap(List<int> nums, int k) {
// 初始化小顶堆,将数组的前 k 个元素入堆
MinHeap heap = MinHeap(nums.sublist(0, k));
// 从第 k+1 个元素开始,保持堆的长度为 k
for (int i = k; i < nums.length; i++) {
// 若当前元素大于堆顶元素,则将堆顶元素出堆、当前元素入堆
if (nums[i] > heap.peek()) {
heap.pop();
heap.push(nums[i]);
}
}
return heap;
}
/* 基于堆查找数组中最大的 k 个元素 */
fn top_k_heap(nums: Vec<i32>, k: usize) -> BinaryHeap<Reverse<i32>> {
// BinaryHeap 是大顶堆,使用 Reverse 将元素取反,从而实现小顶堆
let mut heap = BinaryHeap::<Reverse<i32>>::new();
// 将数组的前 k 个元素入堆
for &num in nums.iter().take(k) {
heap.push(Reverse(num));
}
// 从第 k+1 个元素开始,保持堆的长度为 k
for &num in nums.iter().skip(k) {
// 若当前元素大于堆顶元素,则将堆顶元素出堆、当前元素入堆
if num > heap.peek().unwrap().0 {
heap.pop();
heap.push(Reverse(num));
}
}
heap
}
/* 元素入堆 */
void pushMinHeap(MaxHeap *maxHeap, int val) {
// 元素取反
push(maxHeap, -val);
}
/* 元素出堆 */
int popMinHeap(MaxHeap *maxHeap) {
// 元素取反
return -pop(maxHeap);
}
/* 访问堆顶元素 */
int peekMinHeap(MaxHeap *maxHeap) {
// 元素取反
return -peek(maxHeap);
}
/* 取出堆中元素 */
int *getMinHeap(MaxHeap *maxHeap) {
// 将堆中所有元素取反并存入 res 数组
int *res = (int *)malloc(maxHeap->size * sizeof(int));
for (int i = 0; i < maxHeap->size; i++) {
res[i] = -maxHeap->data[i];
}
return res;
}
/* 基于堆查找数组中最大的 k 个元素的函数 */
int *topKHeap(int *nums, int sizeNums, int k) {
// 初始化小顶堆
// 请注意:我们将堆中所有元素取反,从而用大顶堆来模拟小顶堆
int *empty = (int *)malloc(0);
MaxHeap *maxHeap = newMaxHeap(empty, 0);
// 将数组的前 k 个元素入堆
for (int i = 0; i < k; i++) {
pushMinHeap(maxHeap, nums[i]);
}
// 从第 k+1 个元素开始,保持堆的长度为 k
for (int i = k; i < sizeNums; i++) {
// 若当前元素大于堆顶元素,则将堆顶元素出堆、当前元素入堆
if (nums[i] > peekMinHeap(maxHeap)) {
popMinHeap(maxHeap);
pushMinHeap(maxHeap, nums[i]);
}
}
int *res = getMinHeap(maxHeap);
// 释放内存
delMaxHeap(maxHeap);
return res;
}
/* 基于堆查找数组中最大的 k 个元素 */
fun topKHeap(nums: IntArray, k: Int): Queue<Int> {
// 初始化小顶堆
val heap = PriorityQueue<Int>()
// 将数组的前 k 个元素入堆
for (i in 0..<k) {
heap.offer(nums[i])
}
// 从第 k+1 个元素开始,保持堆的长度为 k
for (i in k..<nums.size) {
// 若当前元素大于堆顶元素,则将堆顶元素出堆、当前元素入堆
if (nums[i] > heap.peek()) {
heap.poll()
heap.offer(nums[i])
}
}
return heap
}
### 基于堆查找数组中最大的 k 个元素 ###
def top_k_heap(nums, k)
# 初始化小顶堆
# 请注意:我们将堆中所有元素取反,从而用大顶堆来模拟小顶堆
max_heap = MaxHeap.new([])
# 将数组的前 k 个元素入堆
for i in 0...k
push_min_heap(max_heap, nums[i])
end
# 从第 k+1 个元素开始,保持堆的长度为 k
for i in k...nums.length
# 若当前元素大于堆顶元素,则将堆顶元素出堆、当前元素入堆
if nums[i] > peek_min_heap(max_heap)
pop_min_heap(max_heap)
push_min_heap(max_heap, nums[i])
end
end
get_min_heap(max_heap)
end
可视化运行
总共执行了 \(n\) 轮入堆和出堆,堆的最大长度为 \(k\) ,因此时间复杂度为 \(O(n \log k)\) 。该方法的效率很高,当 \(k\) 较小时,时间复杂度趋向 \(O(n)\) ;当 \(k\) 较大时,时间复杂度不会超过 \(O(n \log n)\) 。
另外,该方法适用于动态数据流的使用场景。在不断加入数据时,我们可以持续维护堆内的元素,从而实现最大的 \(k\) 个元素的动态更新。