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

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

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

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

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

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

---

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        //1、mapwords的k,v赋值
        HashMap<String,Integer> mapwords = new HashMap<>();
        List<String> res = new ArrayList<>();
        for(int i = 0;i<words.length;i++){
            mapwords.put(words[i],mapwords.getOrDefault(words[i],0)+1);
        }
        //2、建立小根堆
        PriorityQueue<Map.Entry<String,Integer>> minHeap = new PriorityQueue<>(new Comparator<Map.Entry<String,Integer>>(){
            @Override
            public int compare(Map.Entry<String,Integer> o1,Map.Entry<String,Integer> o2){
                if(o1.getValue().equals(o2.getValue())) return o2.getKey().compareTo(o1.getKey());//v一样，字典顺序大的在前面
                return o1.getValue().compareTo(o2.getValue());//建立小根堆
            }
        });
        //3、遍历Map
        Set<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);
                }else if(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);
                    }
                }
            }
        }
        int heapsize = minHeap.size();
        for(int i = 0;i<heapsize;i++){
            res.add(minHeap.poll().getKey());
        }
        Collections.reverse(res);
        return res;
    }
}

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

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

HashMap<String,Integer> mapwords = new HashMap<>();
for(int i = 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 = new PriorityQueue<>(new Comparator<Map.Entry<String,Integer>>(){
    @Override
    public int compare(Map.Entry<String,Integer> o1,Map.Entry<String,Integer> o2){
        if(o1.getValue().equals(o2.getValue()))
            return o2.getKey().compareTo(o1.getKey()); // 同频：字典序大的更差，要更靠近堆顶
        return o1.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);
        }else if(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 频率相同：再看字典序是否更小

else if(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 个单词：

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

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

for(int i=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)
• 空间：HashMap O(m) + 堆 O(k)

满足进阶要求。

---

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

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

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

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

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

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

---

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