优先级队列实战：四大经典算法题解析

三、692. 前 K 个高频单词

题目描述

返回出现频率最高的 K 个单词。如果频率相同，按字典序从小到大排列。

思路解析

1. 先用哈希表统计每个单词的频率。
2. 使用大小为 K 的小根堆来维护 Top K 元素。
3. 自定义比较器：优先比较频率（小根堆），频率相同时比较字符串字典序（大根堆逻辑，即字典序小的排在前面，但在小根堆中意味着字典序大的应该被弹出，这里需要注意逻辑反转）。 修正：题目要求频率相同字典序小的在前。我们维护一个小根堆，堆顶是'最小'的元素。对于 Top K，我们需要保留'最大'的 K 个。所以比较逻辑应该是：频率高的优先，频率相同字典序小的优先。但在小根堆中，我们希望把'最差'的踢出去。因此，如果当前元素比堆顶'好'，就替换。或者更简单地，直接用小根堆存 Top K，堆顶是这 K 个里面'最差'的。如果新元素比堆顶'好'，则替换堆顶。 比较规则：频率低者小；频率相同，字典序大者小（因为字典序大的应该被优先淘汰，留在堆里的是字典序小的）。

参考实现

// 时间复杂度 O(N log K)，空间复杂度 O(N)
class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> count = new HashMap<>();
        for (String word : words) {
            count.put(word, count.getOrDefault(word, 0) + 1);
        }

        // 小根堆：频率低的在顶；频率相同，字典序大的在顶（以便淘汰）
        PriorityQueue<String> heap = new PriorityQueue<>((w1, w2) -> {
            if (count.get(w1) != count.get(w2)) {
                return count.get(w1) - count.get(w2);
            } else {
                return w2.compareTo(w1); // 字典序大的视为更小，先出堆
            }
        });

        for (String word : count.keySet()) {
            heap.offer(word);
            if (heap.size() > k) {
                heap.poll();
            }
        }

        List<String> result = new ArrayList<>();
        while (!heap.isEmpty()) {
            result.add(heap.poll());
        }
        Collections.reverse(result);
        return result;
    }
}

四、295. 数据流的中位数

题目描述

实现一个数据结构，支持添加数字和查找中位数。

思路解析

利用两个堆来平衡数据：一个大根堆存储较小的一半数据，一个小根堆存储较大的一半数据。

• 保持两个堆的大小平衡（差不超过 1）。
• 大根堆堆顶 <= 小根堆堆顶。
• 奇数个元素时，中位数在较大的那个堆顶；偶数个时，为两个堆顶的平均值。

参考实现

// 时间复杂度 O(log N)，空间复杂度 O(N)
class MedianFinder {
    private PriorityQueue<Integer> maxHeap; // 大根堆
    private PriorityQueue<Integer> minHeap; // 小根堆

    public MedianFinder() {
        maxHeap = new PriorityQueue<>((a, b) -> b - a);
        minHeap = new PriorityQueue<>();
    }

    public void addNum(int num) {
        // 默认先放入大根堆，再调整平衡
        maxHeap.offer(num);
        minHeap.offer(maxHeap.poll());

        // 保持大小平衡
        if (maxHeap.size() < minHeap.size()) {
            maxHeap.offer(minHeap.poll());
        }
    }

    public double findMedian() {
        if (maxHeap.size() == minHeap.size()) {
            return (maxHeap.peek() + minHeap.peek()) / 2.0;
        } else {
            return maxHeap.peek();
        }
    }
}