Top-K 问题：为什么小顶堆刚好够用

给定长度为 n 的数组，求其中最大的 K 个元素。这是面试与工程里都很常见的问题。 最朴素的思路是先排序再取后 K 个，复杂度 O(n log n)。当 K 远小于 n 时，有没有更省的办法？

维护「当前最小的 K 个大数」

想象你手里最多只能拿 K 张牌。从左到右扫描数组，每来一个新数 x：

• 若堆中元素不足 K 个，直接放入；
• 若已满且 x 大于堆顶（当前 K 个里最小的那个），弹出堆顶再放入 x；
• 否则忽略 x。

扫描结束后，堆中恰好是原数组最大的 K 个元素。这里用的是小顶堆： 堆顶永远是「目前入选的 K 个数里最弱的」，方便与新元素比较。

复杂度

每个元素最多一次入堆、一次出堆，堆大小恒为 K，单次操作 O(log K)，总时间 O(n log K)。 当 K = O(1) 或 K = O(log n) 时，这比全排序划算得多。

与快速选择（Quickselect）的对比

Floyd 的 quickselect 期望 O(n) 找到第 K 大，但最坏 O(n²)。 工程上若需要流式输入、或需要随时知道「当前 Top-K」的集合，堆更自然； 若只需一次性求第 K 大且能接受随机化，quickselect 往往更快。

Python 示意

import heapq

def top_k(nums: list[int], k: int) -> list[int]:
    heap: list[int] = []
    for x in nums:
        if len(heap) < k:
            heapq.heappush(heap, x)
        elif x > heap[0]:
            heapq.heapreplace(heap, x)
    return heap

标准库 heapq.nlargest(k, nums) 在 k 较小时内部也会走堆路线； k 接近 n 时可能退化为排序，这是实现层面的自适应优化。