堆设计：中位数维护

数据流中的第 K 大元素（LeetCode 703）

小顶堆，维持大小恰好为 K，堆顶就是第 K 大：

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

    public KthLargest(int k, int[] nums) {
        this.k = k;
        minHeap = new PriorityQueue<>(k);
        for (int num : nums) add(num);
    }
    public int add(int val) {
        minHeap.offer(val);
        if (minHeap.size() > k) minHeap.poll();
        return minHeap.peek();
    }
}

前 K 个高频元素（LeetCode 347）

频次统计后用小顶堆（按频次）保留 Top K：

public int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> freq = new HashMap<>();
    for (int n : nums) freq.merge(n, 1, Integer::sum);
    // 小顶堆按频次，维持 k 个
    PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
    for (Map.Entry<Integer, Integer> e : freq.entrySet()) {
        pq.offer(new int[]{e.getKey(), e.getValue()});
        if (pq.size() > k) pq.poll();
    }
    int[] result = new int[k];
    for (int i = k - 1; i >= 0; i--) result[i] = pq.poll()[0];
    return result;
}

桶排序 O(n) 方案：

public int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> freq = new HashMap<>();
    for (int n : nums) freq.merge(n, 1, Integer::sum);
    List<Integer>[] bucket = new List[nums.length + 1];
    for (Map.Entry<Integer, Integer> e : freq.entrySet()) {
        int f = e.getValue();
        if (bucket[f] == null) bucket[f] = new ArrayList<>();
        bucket[f].add(e.getKey());
    }
    List<Integer> result = new ArrayList<>();
    for (int i = bucket.length - 1; i >= 0 && result.size() < k; i--) {
        if (bucket[i] != null) result.addAll(bucket[i]);
    }
    return result.stream().mapToInt(Integer::intValue).toArray();
}

设计推文排行榜（LeetCode 1244，设计题）

使用大顶堆合并多个用户的帖子流，取前 10：

class Twitter {
    private Map<Integer, List<int[]>> tweets = new HashMap<>();  // userId → [时间戳, tweetId]
    private Map<Integer, Set<Integer>> follows = new HashMap<>();
    private int timestamp = 0;

    public void postTweet(int userId, int tweetId) {
        tweets.computeIfAbsent(userId, k -> new ArrayList<>()).add(new int[]{timestamp++, tweetId});
    }
    public List<Integer> getNewsFeed(int userId) {
        // 大顶堆按时间排序
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        Set<Integer> users = new HashSet<>(follows.getOrDefault(userId, new HashSet<>()));
        users.add(userId);
        for (int uid : users) {
            List<int[]> t = tweets.getOrDefault(uid, new ArrayList<>());
            for (int[] tweet : t) pq.offer(tweet);
        }
        List<Integer> result = new ArrayList<>();
        while (!pq.isEmpty() && result.size() < 10) result.add(pq.poll()[1]);
        return result;
    }
    public void follow(int followerId, int followeeId) {
        follows.computeIfAbsent(followerId, k -> new HashSet<>()).add(followeeId);
    }
    public void unfollow(int followerId, int followeeId) {
        follows.getOrDefault(followerId, new HashSet<>()).remove(followeeId);
    }
}

总结