Top-K问题在内存受限场景下采用边读边筛的堆算法，空间复杂度O(k)、时间复杂度O(n log k)；小根堆求最大K，大根堆求最小K；三步法为初始化建堆、扫描替换、输出结果；需处理k超长、重复值、比较器及并发等边界情况。

Top-K问题在内存受限场景下，核心不是“全量加载再排序”，而是“边读边筛”。关键在于用固定大小的堆做动态过滤，把空间复杂度从 O(n) 压到 O(k)，时间复杂度稳定在 O(n log k)。

为什么优先级队列比全排序更省内存

全排序需一次性载入全部数据（比如100亿个整数≈40GB），而优先级队列只维护最多 k 个元素的堆结构。例如找 Top 10，内存中始终只有 10 个数+少量堆管理开销，与原始数据总量无关。

• 小根堆用于求 Top K 最大值：堆顶是最小候选，新数更大就替换堆顶
• 大根堆用于求 Top K 最小值：堆顶是最大候选，新数更小就替换堆顶
• Java 的 PriorityQueue 默认就是小根堆；Python 的 heapq 默认是最小堆，求最大 K 需存负值或改用 heapq.nlargest

处理超大数组的三步落地法

不依赖完整数据加载，适合流式或分块读取场景：

• 初始化阶段：读前 k 个元素，构建初始堆（如小根堆）
• 扫描替换阶段：逐个读后续元素，若大于堆顶（小根堆）则 pop 堆顶 + push 新值
• 输出阶段：堆中 k 个元素即为结果，按需排序输出（堆内无序，但保证是 Top K）

应对边界与异常的实操要点

真实系统中容易踩坑的地方：

• k 超出数组长度时，应直接返回全部元素，而非报错或截断
• 含重复值时，堆不自动去重，逻辑上“第3大”和“前3大”含义不同，需明确业务定义
• C++/Java 中注意堆比较器写法：大根堆需显式传 Comparator.reverseOrder() 或自定义比较逻辑
• 多线程环境建议用 PriorityBlockingQueue，避免并发修改异常

扩展：当数据无法单机加载时怎么办

若连 k 个元素都无法常驻内存（极端情况），可结合分治策略：

• 先按哈希（如 key % 100）将原始数据拆成 100 个小文件
• 每份单独跑 Top K，得到 100 组“局部 Top K”（共 100×k 条）
• 合并这 100×k 条，再做一次全局 Top K，最终结果准确