前 K 个高频元素如何用堆解决？

简化版

先用哈希表统计每个元素出现次数，再用大小为 K 的小顶堆按频次维护当前频率最高的 K 个元素。堆顶是这 K 个候选里频次最低的元素，新元素频次更高时替换它。

详细版

前 K 个高频元素比普通 Top K 多了一步：比较键不是元素值，而是出现频次。

步骤：

扫描数组，用 HashMap<元素, 次数> 统计频次。
遍历 map，把 (元素, 频次) 放入小顶堆。
堆大小超过 K 时弹出堆顶，也就是当前候选中频次最低的元素。
遍历结束后，堆里就是前 K 个高频元素。

int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> freq = new HashMap<>();
    for (int x : nums) freq.put(x, freq.getOrDefault(x, 0) + 1);

    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
    for (Map.Entry<Integer, Integer> e : freq.entrySet()) {
        pq.offer(new int[]{e.getKey(), e.getValue()});
        if (pq.size() > k) pq.poll();
    }

    int[] ans = new int[pq.size()];
    for (int i = ans.length - 1; i >= 0; i--) ans[i] = pq.poll()[0];
    return ans;
}

若数组长度为 n，不同元素个数为 m，统计频次 O(n)，堆维护 O(m log K)，空间 O(m + K)。如果 K 接近 m，桶排序也常被追问。

完整版教学

一、这题为什么不是直接对元素值建堆

题目问的是“出现频率最高”，不是“数值最大”。例如数组 [100, 1, 1, 2, 2, 2]，数值最大的 100 只出现 1 次，而高频元素是 2。比较键必须从元素值切换成频次，这就是本题和普通 Top K 的第一层区别。

所以第一步一定是频次统计。没有频次表，堆就不知道该按什么排序。哈希表负责把原始数组压缩成 (元素, 次数)，堆负责从这些键值对中选出频次最高的 K 个。

nums = [1,1,1,2,2,3]
freq:
  1 -> 3
  2 -> 2
  3 -> 1

Top 2 高频元素：1, 2

二、为什么用小顶堆维护高频候选

和普通 Top K 一样，求“频次最高的 K 个”时，堆顶应该放候选集合里最弱的元素，也就是频次最低的那个。这样新元素进来时，只要看它是否比堆顶频次高，就能决定是否替换。

目标	堆大小	比较键	堆顶含义
前 K 个高频元素	K	出现次数	当前候选中频次最低
最大 K 个数值	K	元素值	当前候选中数值最低
最小 K 个数值	K	元素值	当前候选中数值最高

如果用大顶堆，也可以把所有 (元素, 频次) 都放进去，再弹 K 次，复杂度是 O(m log m)。大小为 K 的小顶堆只保留候选，复杂度是 O(m log K)，当 K 远小于 m 时更合适。

三、带数字走一遍堆变化

设频次表为：A:5, B:2, C:7, D:3, E:6，要求 K=3。小顶堆按频次排序，堆顶是候选里频次最低的。

放 A(5): [A5]
放 B(2): [B2, A5]
放 C(7): [B2, A5, C7]       候选 A,C,B
放 D(3): 先入后 size=4，弹 B2 -> [D3, A5, C7]
放 E(6): 先入后 size=4，弹 D3 -> [A5, E6, C7]

最终 Top 3：A(5), E(6), C(7)

注意最终堆内部不一定按频次降序排列。如果题目要求输出顺序也按频次从高到低，还要把结果再排序或倒序弹出后整理。

四、桶排序为什么也常被拿来比较

频次最大不会超过 n，因此可以建 n + 1 个桶，bucket[f] 存所有出现 f 次的元素，然后从高频桶往低频桶收集 K 个。桶排序时间可以做到 O(n)，但需要额外桶数组，且实现上要处理大量空桶。

freq:
  1 -> 3
  2 -> 2
  3 -> 1

bucket[1] = [3]
bucket[2] = [2]
bucket[3] = [1]
从 3 往 1 扫，取到 [1,2]

面试回答可以这样比较：堆法通用、空间与 K 有关、适合大 m 小 K；桶法理论线性、适合频次范围明确且能接受桶空间。两者都建立在哈希统计之上。

五、工程边界：并列频次、输出顺序和大数据

如果多个元素频次相同，题目通常允许任意顺序；如果要求按数值或首次出现顺序打破平局，比较器必须明确写出来。比较器不完整会导致线上结果不稳定，尤其在 Java PriorityQueue 中，相同优先级元素的弹出顺序没有稳定性保证。

PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {
    if (a[1] != b[1]) return Integer.compare(a[1], b[1]);
    return Integer.compare(a[0], b[0]); // 平局时按元素值
});

如果数据非常大，单机内存放不下频次表，就要先做分片统计或使用外部存储聚合，再对聚合后的频次做 Top K。堆解决的是候选选择，不负责消除统计阶段的内存压力。

六、常见误区与追问

记忆钩子：这题有两层压缩，先用哈希表把数组压成频次，再用小顶堆把频次压成 K 个候选。

这一节面试官通常会围绕 2 个边界继续追问：比较键到底是不是频次，以及输出顺序是否有额外要求。回答时要先把“统计阶段”和“筛选阶段”拆开，再说明堆顶为什么代表最低频候选，而不是把普通 Top K 模板原样套过来。

误区：直接对原数组元素建堆即可。 原数组没有频次信息，堆无法知道谁出现得多。
误区：堆顶应该是最高频元素。 大小为 K 的小顶堆里，堆顶是当前候选中最低频的淘汰门槛。
误区：最终堆数组就是按频次降序。 堆只保证堆顶，不保证整体排序。
追问：K 接近不同元素个数时堆还划算吗？ 优势会变小，可以考虑桶排序或直接排序频次表。
追问：并列频次怎么处理？ 看题目要求；无要求可任意，有要求必须写进比较器。
追问：复杂度里的 m 是什么？ m 是不同元素个数，堆遍历的是频次表而不是原数组的每个位置。

七、加强记忆

前 K 个高频元素的主线是“先统计，再筛选”。哈希表把每个元素映射到出现次数，大小为 K 的小顶堆把“当前最高频 K 个候选”维护住，堆顶就是候选中最低频的门槛。新频次高于门槛就替换，低于门槛就丢弃。记忆时把它和普通 Top K 对照：普通 Top K 的比较键是元素值，本题的比较键是频次；其他维护候选的思想完全一致。

简化版

详细版