优先队列核心原理与经典算法题实战

2. 数据流中的第 K 大元素

参考题目： 703. 数据流中的第 K 大元素

思路分析： 维护一个大小为 K 的小根堆。堆中保存的是目前为止遇到的最大的 K 个数。当新元素加入时，如果比堆顶小，则忽略；如果比堆顶大，则替换堆顶并调整堆。这样堆顶始终是当前第 K 大的数。

参考实现：

import java.util.PriorityQueue;

class KthLargest {
    private PriorityQueue<Integer> heap;
    private int k;

    public KthLargest(int k, int[] nums) {
        this.k = k;
        this.heap = new PriorityQueue<>();
        for (int num : nums) {
            add(num);
        }
    }

    public int add(int val) {
        heap.offer(val);
        if (heap.size() > k) {
            heap.poll();
        }
        return heap.peek();
    }
}

时间复杂度：O(n log k)，空间复杂度：O(k)

3. 前 K 个高频单词

参考题目： 692. 前 K 个高频单词

思路分析： 先统计词频，再用堆筛选前 K 个。这里需要自定义比较规则：频率高的优先；若频率相同，字典序小的优先（注意题目要求）。由于 Java 的 PriorityQueue 默认是小根堆，我们需要根据需求调整 Comparator。

参考实现：

import java.util.*;

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> map = new HashMap<>();
        for (String w : words) {
            map.put(w, map.getOrDefault(w, 0) + 1);
        }

        // 小根堆：频率低在前；频率相同时，字典序大在前（因为要逆序输出）
        PriorityQueue<Map.Entry<String, Integer>> heap = new PriorityQueue<>((a, b) -> {
            if (!a.getValue().equals(b.getValue())) {
                return a.getValue() - b.getValue();
            } else {
                return b.getKey().compareTo(a.getKey());
            }
        });

        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            heap.offer(entry);
            if (heap.size() > k) {
                heap.poll();
            }
        }

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

时间复杂度：O(N log K)，空间复杂度：O(N)

4. 数据流的中位数

参考题目： 295. 数据流的中位数

思路分析： 维护两个堆：一个大根堆存较小的一半，一个小根堆存较大的一半。保证两个堆的大小平衡（差不超过 1）。插入时根据数值大小决定放入哪个堆，然后调整平衡。查询中位数时，若总数为奇数，取多的一方的堆顶；若为偶数，取两堆顶的平均值。

参考实现：

import java.util.PriorityQueue;

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 的元素数量总是 >= minHeap
        if (maxHeap.isEmpty() || num <= maxHeap.peek()) {
            maxHeap.offer(num);
        } else {
            minHeap.offer(num);
        }

        // 平衡两个堆的大小
        if (maxHeap.size() > minHeap.size() + 1) {
            minHeap.offer(maxHeap.poll());
        } else if (minHeap.size() > maxHeap.size()) {
            maxHeap.offer(minHeap.poll());
        }
    }

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

时间复杂度：O(log n)，空间复杂度：O(n)