核心要点

  • 求最大的 K 个：维护大小为 k 的「最小堆」，堆顶是这 k 个里最小者

  • 流程：堆未满直接入堆；堆满时若新元素 > 堆顶则弹出堆顶再入堆，否则丢弃

  • 复杂度：n 个元素各做一次 O(log k) 堆操作，时间 O(n log k)，空间 O(k)，适合海量数据

标准回答

Top-K 问题（找最大或最小的 K 个元素）的高效解法是维护一个大小固定为 k 的堆。求「最大的 K 个」时用最小堆：堆顶恰好是当前 k 个候选里最小的，遍历到新元素时，若堆未满直接放入，若已满则只有当新元素大于堆顶时才替换堆顶——这样能保证堆里始终是已遍历元素中最大的 k 个。相比全排序的 O(n log n)，这种做法是 O(n log k)，且只需 O(k) 空间，特别适合数据量远大于 k 的场景。Python 用 heapq（最小堆）实现：

python
import heapq


def top_k_largest(nums, k):
    # 返回最大的 k 个元素，用大小为 k 的最小堆
    heap = []
    for x in nums:
        if len(heap) < k:
            heapq.heappush(heap, x)            # 堆未满，直接入堆
        elif x > heap[0]:                      # 比堆顶（最小者）大才替换
            heapq.heapreplace(heap, x)         # 弹出堆顶并压入 x，一次完成
    return sorted(heap, reverse=True)


if __name__ == '__main__':
    print(top_k_largest([3, 1, 5, 12, 2, 11], 3))  # [12, 11, 5]
    # 也可直接用库函数验证
    print(heapq.nlargest(3, [3, 1, 5, 12, 2, 11]))  # [12, 11, 5]

常见误区

⚠️ 常见踩坑

求「最大的 K 个」要用最小堆（堆顶最小才方便淘汰），别用最大堆；只有 x > heap[0] 才替换，写成 >= 会做无意义的替换但不影响正确性，写成用最大堆维护则复杂度退化。

追问

追问 1：为什么是最小堆而不是最大堆？复杂度对比全排序？

因为要不断淘汰当前候选里最小的那个，最小堆的堆顶 O(1) 可见、O(log k) 可换。整体 O(n log k)，优于全排序 O(n log n)（当 k 远小于 n 时）。若用最大堆需弹出 k 次取 Top-K，建堆 O(n)、取 k 次 O(k log n)。

追问 2：还有没有更快的 Top-K 解法？

用快速选择（Quickselect，基于快排 partition）可在平均 O(n) 时间找到第 k 大元素并划分出 Top-K，但最坏 O(n²)（可随机化或用中位数的中位数避免）。堆法的优势是天然支持流式/海量数据，无需把全部数据载入内存。

延伸学习

与本题相关的知识库文章、术语、工具与行业资讯。

🎯 相关面试题