跳转至

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 所示。

  1. 初始化一个小顶堆,其堆顶元素最小。
  2. 先将数组的前 \(k\) 个元素依次入堆。
  3. 从第 \(k + 1\) 个元素开始,若当前元素大于堆顶元素,则将堆顶元素出堆,并将当前元素入堆。
  4. 遍历完成后,堆中保存的就是最大的 \(k\) 个元素。

图 8-8   基于堆寻找最大的 k 个元素

图解 8-8:用小顶堆寻找 Top-k

维护至多 k 个候选,用其中最小值与后续元素比较,逐步保留最大的 k 个值。

本例 k=3,输入数组及其索引见下表。指针 i 表示输入索引;heap 是小顶堆的层序数组,堆索引 0 存放最小候选,左、右子节点分别在堆索引 1、2(若存在)。输入索引表示元素来源,堆索引表示当前存储位置。

先把前 k 个输入依次入堆,随后逐个比较:当前值大于堆顶时,先弹出堆顶再加入当前值,否则跳过。表格按步号命名;比较或跳过时堆未改变,按表名引用相应的候选与来源索引。

堆顶是候选中最小的值。遇到更大的新值时,用它替换堆顶,仍能保留已处理输入中最大的 k 个值。查看堆顶用 O(1) 时间,入堆或出堆调整用 O(log k) 时间。

输入数组与索引
输入索引值
01
17
26
33
42
  1. 将1加入空堆

    指针 i=0,读取值 1 加入空堆。当前只有 1 个候选 [1],堆顶为 1。

    第 1 步候选:加入 1 后
    堆数组索引值来自输入索引
    010
  2. 将7入堆

    指针 i=1,读取值 7 入堆,挂在堆索引 1。父节点 1 小于 7,无须上浮;当前 2 个候选为 [1, 7],堆顶为 1。

    第 2 步候选:加入 7 后
    堆数组索引值来自输入索引
    010
    171
  3. 将6入堆,初始候选齐备

    指针 i=2,读取值 6 入堆,挂在堆索引 2。当前 3 个候选为 [1, 7, 6],堆顶为 1;前 k=3 个输入已全部入堆,接下来比较后续元素。

    第 3 步候选:初始三项齐备
    堆数组索引值来自输入索引
    010
    171
    262
  4. 比较当前3与堆顶1

    指针 i=3,当前值 3 大于最小候选 1,准备替换。本步仅比较,尚未弹出或加入元素;3 个候选仍是 [1, 7, 6],堆顶为 1。候选与来源索引见“第 3 步候选:初始三项齐备”表。

  5. 弹出旧堆顶1

    指针仍为 i=3,先弹出旧堆顶 1,剩余元素调整为 [6, 7],堆顶暂为 6。当前只有 k−1=2 个候选,值 3 尚待入堆;这是替换的中间状态,没有漏掉结果,也尚未完成这一轮。

    第 5 步候选:弹出 1 后的中间态
    堆数组索引值来自输入索引
    062
    171
  6. 将3入堆

    指针仍为 i=3,将值 3 入堆并上浮至根,恢复 k=3 个候选 [3, 7, 6],新堆顶为 3。这三个候选是前 4 个输入中的最大三个值。

    第 6 步候选:加入 3 后
    堆数组索引值来自输入索引
    033
    171
    262
  7. 比较当前2与堆顶3

    指针 i=4,当前值 2 小于堆顶 3,不满足替换条件。本步仅比较,3 个候选仍为 [3, 7, 6]。候选与来源索引见“第 6 步候选:加入 3 后”表。

  8. 跳过2

    指针 i=4,由于 2 小于堆顶 3,跳过它,不做出堆或入堆。3 个候选仍为 [3, 7, 6],堆顶为 3;全部输入已处理。候选与来源索引见“第 6 步候选:加入 3 后”表。

  9. 返回三个候选

    遍历结束,无当前指针,直接返回小顶堆 [3, 7, 6]。三个候选的输入来源见下表;堆顶为 3,但左右子节点 7 和 6 不必升序,这里没有再做排序。

    第 9 步最终返回的候选与来源
    堆数组索引值来自输入索引
    033
    171
    262

堆内至多保留 k 个候选,空间复杂度为 O(k),总时间复杂度为 O(n log k)。

示例代码如下:

top_k.py
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
top_k.cpp
/* 基于堆查找数组中最大的 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;
}
top_k.java
/* 基于堆查找数组中最大的 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;
}
top_k.cs
/* 基于堆查找数组中最大的 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;
}
top_k.go
/* 基于堆查找数组中最大的 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
}
top_k.swift
/* 基于堆查找数组中最大的 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
}
top_k.js
/* 元素入堆 */
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);
}
top_k.ts
/* 元素入堆 */
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);
}
top_k.dart
/* 基于堆查找数组中最大的 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;
}
top_k.rs
/* 基于堆查找数组中最大的 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
}
top_k.c
/* 元素入堆 */
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;
}
top_k.kt
/* 基于堆查找数组中最大的 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
}
top_k.rb
### 基于堆查找数组中最大的 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\) 个元素的动态更新。

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