Top K 要回答的是”从 N 个元素中挑出最大（或最小）的 K 个”，它不是一个具体算法，而是一类问题：数据能否全进内存、一次性还是流式、结果要不要有序，每个约束都把最优解推向不同方向。真正要掌握的是四条路线——排序、堆、快速选择、分治合并——以及它们各自的适用边界。

它解决什么问题

搜索引擎的热词榜、监控系统的 Top 错误码、推荐系统的候选截断，本质都是 Top K。问题的关键变量有三个：K 与 N 的相对大小、数据能否全部驻留内存、是否需要输出有序结果。当 K 远小于 N 时，为”挑出 K 个”付出 O(N log N) 的全排序是明显浪费——Top K 的全部技巧都围绕”如何避免排完整个数组”展开。

核心原理

  • 全排序：排完取前 K 个，O(N log N)。优点是代码一行、结果天然有序；缺点是杀鸡用牛刀，N 大时不可接受。
  • 堆：维护一个大小恒为 K 的优先队列扫一遍数据，O(N log K)、空间 O(K)，天然支持数据流。
  • 快速选择（QuickSelect）：借用快排分区，枢轴归位后只递归含有目标名次的一侧，期望 O(N)。
  • 分治 + 哈希：海量数据按 key 分片，各片独立求局部 Top K，再合并全局候选。这是单机内存装不下时唯一能横向扩展的方案。

深入机制

堆：大小顶堆的选择逻辑

口诀是”求最大 K 个用小顶堆，求最小 K 个用大顶堆”。以小顶堆求最大 K 个为例：堆里始终装着当前见过的最大 K 个元素，堆顶是这 K 个里最小的”门槛”。新元素只有比门槛大才值得进堆——进堆后弹出堆顶，门槛自动抬高。这个”门槛单调抬升”的性质，保证扫完一遍后堆里剩下的就是全局前 K：

int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> heap = new PriorityQueue<>(k);  // 默认小顶堆
    for (int x : nums) {
        heap.offer(x);
        if (heap.size() > k) heap.poll();  // 淘汰候选集中最小者
    }
    return heap.peek();  // 堆顶即第 K 大
}

每次调整 O(log K)，总时间 O(N log K)、空间 O(K)。Java 的 PriorityQueue 默认是小顶堆，自定义比较器别写 (a, b) -> b - a——极端整数相减会溢出，应写 Integer.compare(b, a)。前 K 高频这类题，先用 HashMap 统计频次，再对 (元素, 频次) 做同样的堆扫描。

快速选择：期望 O(N) 的分治

一次分区后枢轴落在下标 p，它左边恰有 p 个更小的元素。若 p 正好是目标名次（升序下第 N-K 位即第 K 大），直接返回；否则只需递归包含目标的一侧，另一侧整段丢弃。每轮处理规模大致减半，总工作量是 n + n/2 + n/4 + … 的等比级数，收敛到约 2n，故期望 O(N)：

int quickSelect(int[] a, int lo, int hi, int target) {
    int p = partition(a, lo, hi);   // 随机枢轴分区，复用快排写法
    if (p == target) return a[p];
    return p < target ? quickSelect(a, p + 1, hi, target)
                      : quickSelect(a, lo, p - 1, target);
}

三个注意点：最坏仍会退化到 O(N²)，随机化枢轴是标配；它会打乱原数组，不能改输入时要先拷贝；它只保证第 K 名就位，前 K 个结果无序，要顺序需补一次 O(K log K) 的排序。

桶计数：频次类 Top K 的线性做法

前 K 高频还有一条更激进的路：频次的值域天然有界（1 到 N），统计完频次后直接按频次建桶——桶 i 装所有出现 i 次的元素，再从最高频桶向低频桶收集，凑够 K 个即停。计数 O(N)、建桶收集 O(N)，整体严格 O(N)，连堆的 log K 因子都省掉了。代价是额外 O(m) 的桶空间（m 为不同元素个数），且这套思路只适用于键的值域有界、可枚举的场景，泛化能力不如堆。

工程实践

海量数据场景（如十亿条日志求 Top 100 热词）的标准解是分治 + 哈希：按 key 的哈希把数据散到 M 个分片，每片内存可装，各自用 HashMap 计数加小顶堆求局部 Top K，再汇总至多 K×M 个候选求全局结果。哈希分片保证同一 key 不跨片，局部 Top K 才可能合并出正确的全局 Top K。两个坑要防：热点 key 让某片数据倾斜，需要二次分片或采样打散；若分片内只保留前 K 候选，要确认这个截断在业务语义下足够精确。数据流场景（边到达边查询）则回到大小为 K 的堆，每个元素 O(log K) 增量维护，无须留存全量。

对比与权衡

方案 时间 额外空间 结果有序 支持数据流 修改输入
全排序 O(N log N) O(log N)~O(N) 是 否 视实现
堆（大小 K） O(N log K) O(K) 否 是 否
快速选择 期望 O(N)，最坏 O(N²) O(log N) 栈 否 否 是
分治 + 哈希 O(N + MK log K) 各片 O(K) 否 可扩展 否

选型决策：一次性内存数据、只要第 K 名，QuickSelect 最快；K 远小于 N 且要边扫边留候选、或数据流式到达，用堆；N 超单机内存，分治加哈希；N 很小或顺便要全序结果，直接排序。

面试视角

为什么求最大 K 个用小顶堆而不是大顶堆？ 堆的作用是维护”当前前 K 候选集”，淘汰时要去掉候选中最差的那个。小顶堆堆顶恰好是候选最小值，一次 O(log K) 完成淘汰；大顶堆堆顶是候选最大值，无法快速定位该淘汰谁。

QuickSelect 期望 O(N) 的依据是什么？ 分区后只递归一侧，随机枢轴保证每轮规模在期望意义下大致减半，总工作量是收敛的等比级数，上限约 2n。

堆和 QuickSelect 怎么选？ 离线数组求第 K 大且允许改数组，QuickSelect 更快；数据流、内存放不下全量、或要持续应答查询，选堆。需要前 K 且有序输出时，两者之后都得补一次 K log K 的排序。

前 K 高频为什么要先统计再入堆？ 因为比较基准是频次而非元素值。先 HashMap 聚合成 (key, count) 再对 count 做 Top K；不同元素个数 m 通常远小于 N，堆扫描开销从 O(N log K) 降到 O(m log K)。

小结

  • Top K 的核心是避免全排序：堆付 O(N log K)、QuickSelect 期望 O(N)，都优于 O(N log N)。
  • 堆的方向一句话：留大用小顶，留小用大顶，堆顶永远是最该被淘汰的那个。
  • QuickSelect 复用快排分区，随机化防退化，但会改数组且结果无序。
  • 超出单机内存时，哈希分片 + 局部 Top K + 全局合并是标准答案，注意热点倾斜。