【码道初阶】近期耗时最长制作【LeetCode692】 前 K 个高频单词：我如何用 HashMap + 小根堆把排序规则“塞进堆里”

692 前 K 个高频单词：我如何用 HashMap + 小根堆把排序规则“塞进堆里”

这道题的规则很明确，但实现时非常容易在细节上出错：

• 按出现频率从高到低
• 频率相同按字典序升序（字典序小的更靠前）
• 进阶希望做到O(n log k)

直觉上如果把所有单词都统计完然后排序，当然能做，但那通常是O(m log m)（m 是不同单词数）。当我想追求进阶复杂度时，最自然的思路就是：

只维护前 k 个候选，而不是把全部候选排序。

这就引出了经典套路：HashMap 统计 + 小根堆维护 TopK。

classSolution{publicList<String>topKFrequent(String[]words,intk){//1、mapwords的k,v赋值HashMap<String,Integer>mapwords=newHashMap<>();List<String>res=newArrayList<>();for(inti=0;i<words.length;i++){mapwords.put(words[i],mapwords.getOrDefault(words[i],0)+1);}//2、建立小根堆PriorityQueue<Map.Entry<String,Integer>>minHeap=newPriorityQueue<>(newComparator<Map.Entry<String,Integer>>(){@Overridepublicintcompare(Map.Entry<String,Integer>o1,Map.Entry<String,Integer>o2){if(o1.getValue().equals(o2.getValue()))returno2.getKey().compareTo(o1.getKey());//v一样，字典顺序大的在前面returno1.getValue().compareTo(o2.getValue());//建立小根堆}});//3、遍历MapSet<Map.Entry<String,Integer>>mapset=mapwords.entrySet();for(Map.Entry<String,Integer>entry:mapset){if(minHeap.size()<k){minHeap.offer(entry);}else{if(minHeap.peek().getValue().compareTo(entry.getValue())<0){//entry的元素的出现次数比小根堆的堆顶元素多minHeap.poll();minHeap.offer(entry);}elseif(minHeap.peek().getValue().equals(entry.getValue())){if(minHeap.peek().getKey().compareTo(entry.getKey())>0){//注意：getKey()的Comparator改变并不改变这里compareTo的含义是：heap顶端的字典序比entry的大//这里的大于 0 指的是 minHeap 顶部的字典序更大；遇到更小（更优）的 entry，它要被弹出，用 entry 替换。//如果不重写该方法，在Size小于K时遇到a-3先进堆，b-3后进堆，reverse之后顺序不对//本来想不reverse,让a-3在前，b-3在后，但是这样遇到了b-3先进，a-3后进（此时小于k），输出的顺序是一定不对的//所以必须要reverse,而这也就导致了必须重写比较方法，使字典顺序更靠后的一定要在堆顶，这样reverse下来就一定是对的顺序minHeap.poll();minHeap.offer(entry);}}}}intheapsize=minHeap.size();for(inti=0;i<heapsize;i++){res.add(minHeap.poll().getKey());}Collections.reverse(res);returnres;}}

1. 先把题目“压缩”：HashMap 统计词频

第一步是把words变成一个更适合排序的数据结构：(word -> count)。

HashMap<String,Integer>mapwords=newHashMap<>();for(inti=0;i<words.length;i++){mapwords.put(words[i],mapwords.getOrDefault(words[i],0)+1);}

这一步干了两件事：

1. 把重复的单词合并了（否则后面堆里会塞进海量重复单词）
2. 把排序依据（count）变成了可直接访问的值

完成后就可以用mapwords.entrySet()拿到一组Map.Entry<String,Integer>，每个 entry 就是一对(单词, 频率)。

2. 小根堆不是用来“取最小”，而是用来“淘汰最差”

很多人第一次用堆做 TopK 会误解：既然要前 K 个高频，为什么不用大根堆？
关键在于复杂度目标：O(n log k)。

如果把所有 entry 都塞进大根堆再弹 k 个，那是O(m log m)，并不优。真正能做到log k的做法是：

维护一个大小最多为 k 的堆，堆顶永远放“当前 k 个候选里最差的那个”。
来了更好的，就把堆顶踢掉。

这就是我选择“小根堆”的原因：小根堆堆顶就是“最小”，我只要把“最差”定义成“最小”，堆顶就自然代表最差。

3. 这题最重要的地方：比较器必须把“最差”放到堆顶

题目最终的好坏定义是：

• 更好：频率更高
• 同频更好：字典序更小

那“更差”就反过来：

• 更差：频率更低
• 同频更差：字典序更大

所以我给小根堆写了这个比较器：

PriorityQueue<Map.Entry<String,Integer>>minHeap=newPriorityQueue<>(newComparator<Map.Entry<String,Integer>>(){@Overridepublicintcompare(Map.Entry<String,Integer>o1,Map.Entry<String,Integer>o2){if(o1.getValue().equals(o2.getValue()))returno2.getKey().compareTo(o1.getKey());// 同频：字典序大的更差，要更靠近堆顶returno1.getValue().compareTo(o2.getValue());// 频率小的更差，要更靠近堆顶}});

这段比较器做的事可以翻译成一句话：

频率按升序（低频更差）；同频 key 按降序（字典序大更差）。

为什么同频要降序？
因为小根堆会把“更小的”放在堆顶，而我希望“字典序更大的那个”更容易成为堆顶（更容易被淘汰），所以必须把 key 的比较方向反过来。

这一步不是“改动String.compareTo的含义”，而是：

定义 PriorityQueue 内部的排序规则，让堆顶的含义符合 TopK 淘汰逻辑。

同时要记住一点：堆的比较器会影响谁成为peek()，但不会影响这句代码本身的语义：

peekKey.compareTo(entryKey)>0

它永远只是判断peekKey字典序是否更大。

4. 遍历 entrySet：维持一个不变量——堆里永远是“当前最优的 k 个”

接下来遍历mapwords.entrySet()，逐个 entry 决定是否进入堆：

for(Map.Entry<String,Integer>entry:mapwords.entrySet()){if(minHeap.size()<k){minHeap.offer(entry);}else{if(minHeap.peek().getValue().compareTo(entry.getValue())<0){minHeap.poll();minHeap.offer(entry);}elseif(minHeap.peek().getValue().equals(entry.getValue())){if(minHeap.peek().getKey().compareTo(entry.getKey())>0){minHeap.poll();minHeap.offer(entry);}}}}

我在脑子里维护的那个“不变量”是：

遍历到当前为止，minHeap 保存的是出现频率最高的 k 个词；如果同频，保存字典序更小的词。
而堆顶永远是其中“最差的那个”。

4.1 堆没满：直接塞

if(minHeap.size()<k)minHeap.offer(entry);

前 k 个候选先收集起来，没有任何淘汰发生。

4.2 堆满：先看频率是否更高

if(peekFreq<entryFreq){poll+offer}

堆顶是“最差”，而频率更低是最差的重要特征。
如果新 entry 频率更高，它一定比堆顶更值得留下，所以踢掉堆顶换成它。

4.3 频率相同：再看字典序是否更小

elseif(peekFreq==entryFreq){if(peekKey>entryKey){poll+offer}}

同频时题目要字典序小的更靠前，也就是更“好”。
如果堆顶 key 更大（字典序更靠后），说明堆顶更差，应当替换掉，让 entry 进堆。

这一段的判断语义非常稳定：

• > 0永远表示堆顶 key 字典序更大
• 所以 entry 字典序更小、更优
• 替换是合理的

注意！

• 注意：getKey()的Comparator改变并不改变这里compareTo的含义是：heap顶端的字典序比entry的大
• 这里的大于 0 指的是 minHeap 顶部的字典序更大；遇到更小（更优）的 entry，它要被弹出，用 entry 替换。
• 如果不重写该方法，在Size小于K时遇到a-3先进堆，b-3后进堆，reverse之后顺序不对
• 本来想不reverse,让a-3在前，b-3在后，但是这样遇到了b-3先进，a-3后进（此时小于k），输出的顺序是一定不对的
• 所以必须要reverse,而这也就导致了必须重写比较方法，使字典顺序更靠后的一定要在堆顶，这样reverse下来就一定是对的顺序
  倒数3 4 5项是本题本人的思考精华所在

5. 取结果时的一个“经典坑”：size 会变，所以要先保存 heapsize

堆维护完成后，取出堆里的 k 个单词：

intheapsize=minHeap.size();for(inti=0;i<heapsize;i++){res.add(minHeap.poll().getKey());}Collections.reverse(res);

这里先把heapsize存下来非常关键。
因为poll()一次，堆 size 就减 1，如果写成：

for(inti=0;i<minHeap.size();i++)

循环条件会随着 poll 变化，导致只弹出一半元素（这就是早期输出不全的根源）。

6. 为什么最后必须 reverse？

小根堆的poll()是按“最小优先”弹出的。
而我把“最差”定义成“最小”，所以 poll 出来的顺序天然是：

从差到好

但题目要求输出顺序是：

从好到差

所以必须：

Collections.reverse(res);

reverse 不是锦上添花，而是这个“小根堆保留 TopK”方案的固定收尾。

7. 这份方案的复杂度

• 统计词频：O(n)
• 不同单词数m
• 遍历每个 entry 最多堆操作一次：O(log k)
• 总体：O(m log k)，通常写作O(n log k)
• 空间：HashMapO(m)+ 堆O(k)

满足进阶要求。

8. 最后把整题浓缩成三句“写代码时的自检清单”

1. 堆顶是不是“最差的那个”？

   • 频率小更差
   • 同频字典序大更差
     比较器必须体现这一点

2. 堆满时替换逻辑是不是只和堆顶比较？

   • 更高频 → 替换
   • 同频更小字典序 → 替换

3. 结果是不是从差到好弹出？如果是，就 reverse。
   以及：取结果时一定别用动态 size 当循环上界。

这套思路不仅能解 692，很多 TopK 题（TopK 频率元素、TopK 最小/最大数、TopK 文件/日志统计）都能直接套用：关键永远是——把“最差”的定义写进比较器，让堆顶永远代表淘汰对象。