Top K 问题怎么用堆解决？求最大的 K 个为什么用小顶堆？

简化版

求「最大的 K 个元素」，用一个大小为 K 的小顶堆：遍历数据，堆没满就加入；满了就拿新元素和**堆顶（这 K 个里最小的）**比，比堆顶大就替换掉堆顶。遍历完，堆里就是最大的 K 个，堆顶是「第 K 大」。时间 O(n log K)，只需 O(K) 空间——比全排序 O(n log n) 快，尤其适合海量数据。求最大用小顶堆、求最小用大顶堆（反直觉但正确）。

详细版

求最大的 K 个（用小顶堆，size K）：

int[] topK(int[] nums, int k) {
    PriorityQueue<Integer> heap = new PriorityQueue<>(); // 默认小顶堆
    for (int x : nums) {
        if (heap.size() < k) heap.offer(x);
        else if (x > heap.peek()) {   // 比 K 个里最小的还大
            heap.poll();              // 淘汰最小的
            heap.offer(x);
        }
    }
    // heap 里就是最大的 K 个，堆顶 heap.peek() 是第 K 大
    return heap.stream().mapToInt(i->i).toArray();
}

需求	用什么堆	堆顶是
最大的 K 个 / 第 K 大	小顶堆（size K）	第 K 大（这 K 个里最小）
最小的 K 个 / 第 K 小	大顶堆（size K）	第 K 小（这 K 个里最大）

完整版教学

一、为什么求「最大 K 个」反而用小顶堆

这是 Top K 最反直觉、也最爱考的点。要求最大的 K 个，我们维护一个只装 K 个元素的小顶堆，堆顶是这 K 个当中最小的。

遍历新元素时，要判断它「配不配进入 Top K」。
判断标准就是：它比当前 K 个里最小的（堆顶）大吗？ 大就说明它够格，把最小的（堆顶）淘汰、它进来；不大就说明它连门槛都够不着，丢弃。
小顶堆的堆顶正好是「门槛值」，O(1) 就能拿到、O(log K) 就能替换。

所以小顶堆的堆顶充当「Top K 的守门员」——只有比门槛高的才放进来，同时踢掉当前最弱的。如果用大顶堆，堆顶是最大值，反而没法高效判断「谁该被淘汰」。求最大用小顶堆、求最小用大顶堆，核心就是「堆顶要放最容易被淘汰的那个」。

二、复杂度：为什么是 O(n log K)

遍历 n 个元素：O(n)。
每个元素最多做一次堆操作（插入或替换）：O(log K)。
总计 O(n log K)，空间 O(K)。

对比「全排序再取前 K」的 O(n log n)：当 K 远小于 n 时（比如从 10 亿数据里取前 100），O(n log K) 明显更快，且只需 O(K) 内存——海量数据、内存放不下时，堆法是标准解（数据可以流式进来，堆里始终只留 K 个）。

三、其它解法对比

全排序：O(n log n)，简单但慢，且要把所有数据读进内存。
堆（size K）：O(n log K)、O(K) 空间，适合海量/流式数据。最常用。
快速选择（QuickSelect）：基于快排 partition，平均 O(n) 找到第 K 大并把前 K 个划到一侧。比堆更快，但要求数据全在内存、会修改数组、最坏 O(n²)，且不适合流式数据。

选择：数据量大/流式/内存受限 → 堆；数据全在内存、只要一次性求第 K 大 → 快速选择（平均 O(n)）。

四、常见变体

第 K 大元素：就是「最大 K 个」小顶堆的堆顶。
前 K 个高频元素：先用哈希表统计频率，再用「按频率的小顶堆」取 Top K（频率当比较键）。
K 个最接近的点 / 值：用大顶堆按「距离」维护 size K，堆顶是当前 K 个里最远的，来了更近的就替换。

框架都一样：维护一个 size K 的堆，堆顶放”最该被淘汰的那个”，新元素和堆顶 PK。

五、易错点

堆的方向别搞反：求最大用小顶堆，求最小用大顶堆。
先判断再替换：满了之后，先和堆顶比较，够格才 poll + offer，不要无脑加。
堆大小恒为 K：始终维持 K 个，超了就淘汰堆顶。

六、常见误区与追问

考点	正确口径
求最大 K 个	维护大小为 K 的小顶堆
求最小 K 个	维护大小为 K 的大顶堆
复杂度	O(n log K)，空间 O(K)

for x in nums:
  if heap.size < k: offer(x)
  else if x > heap.peek:
    poll()
    offer(x)

Top K 反着用堆：求最大 K 个，用小顶堆把候选集合里最小的踢出去。

误区：求最大 K 个必须用大顶堆。 大顶堆适合不断弹出全局最大；维护 K 个最大候选时，小顶堆堆顶是淘汰线。
误区：堆大小可以增长到 n。 Top K 的优势就是堆只保留 K 个元素，空间 O(K)。
误区：Top K 一定要输出有序结果。 堆法得到的是 K 个元素集合，若要求排序，还需要对堆内元素再排序。
追问：K 很接近 n 时还适合堆吗？ 此时 O(n log K) 接近排序成本，可直接排序或用快速选择后处理。
追问：快速选择和堆怎么选？ 快速选择平均 O(n) 但最坏和实现细节更敏感；堆法稳定、适合流式数据。
追问：数据流 Top K 怎么做？ 持续维护一个大小为 K 的小顶堆，每来一个新数按淘汰线更新。

七、加强记忆

Top K 用大小为 K 的堆：求最大 K 个用小顶堆（堆顶=这 K 个里最小=门槛，新元素比它大就替换掉它）、求最小 K 个用大顶堆——口诀「堆顶放最该被淘汰的」。时间 O(n log K)、空间 O(K)，适合海量/流式数据；第 K 大就是小顶堆堆顶。数据全在内存只求一次可用快速选择（平均 O(n)）。

简化版

详细版