Heap Design: Median Maintenance and Ranking Systems

Kth Largest Element in a Stream (LeetCode 703)

Use a Min Heap that maintains precisely K elements. The root of the heap represents the $K$-th largest element in the stream.

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

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

    public int add(int val) {
        minHeap.offer(val);
        // Ensure the heap size remains K
        if (minHeap.size() > k) {
            minHeap.poll();
        }
        return minHeap.peek();
    }
}

Top K Frequent Elements (LeetCode 347)

Approach 1: Min Heap (Priority Queue)

After counting frequencies, use a Min Heap (ordered by frequency) to keep only the K most frequent items.

public int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> frequencyMap = new HashMap<>();
    for (int n : nums) frequencyMap.merge(n, 1, Integer::sum);
    
    // Min Heap based on frequency count
    PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<>(
        Comparator.comparingInt(Map.Entry::getValue)
    );
    
    for (Map.Entry<Integer, Integer> entry : frequencyMap.entrySet()) {
        pq.offer(entry);
        if (pq.size() > k) pq.poll();
    }
    
    int[] topK = new int[k];
    for (int i = k - 1; i >= 0; i--) {
        topK[i] = pq.poll().getKey();
    }
    return topK;
}

Approach 2: Bucket Sort (Optimal O(N))

Since frequencies are bounded by array length, we can use an array of buckets where the index is the frequency.

public int[] topKFrequentBucket(int[] nums, int k) {
    Map<Integer, Integer> freq = new HashMap<>();
    for (int n : nums) freq.merge(n, 1, Integer::sum);
    
    // Buckets: freq -> list of elements with that freq
    List<Integer>[] buckets = new List[nums.length + 1];
    for (var entry : freq.entrySet()) {
        int f = entry.getValue();
        if (buckets[f] == null) buckets[f] = new ArrayList<>();
        buckets[f].add(entry.getKey());
    }
    
    List<Integer> result = new ArrayList<>();
    for (int i = buckets.length - 1; i >= 0 && result.size() < k; i--) {
        if (buckets[i] != null) result.addAll(buckets[i]);
    }
    return result.subList(0, k).stream().mapToInt(i -> i).toArray();
}

Design Twitter News Feed (LeetCode 355)

The news feed is essentially Merging K Sorted Streams (user's tweets + their followees' tweets). Use a Max Heap to pick the 10 most recent posts.

class Twitter {
    private static int globalTimer = 0;
    private static class Tweet {
        int id, time;
        Tweet(int id) { this.id = id; this.time = globalTimer++; }
    }
    
    private final Map<Integer, List<Tweet>> userTweets = new HashMap<>();
    private final Map<Integer, Set<Integer>> follows = new HashMap<>();

    public void postTweet(int userId, int tweetId) {
        userTweets.computeIfAbsent(userId, k -> new ArrayList<>()).add(new Tweet(tweetId));
    }

    public List<Integer> getNewsFeed(int userId) {
        // Max Heap ordered by time (descending)
        PriorityQueue<Tweet> feedHeap = new PriorityQueue<>((a, b) -> b.time - a.time);
        
        // 1. Collect tweets from self
        if (userTweets.containsKey(userId)) {
            feedHeap.addAll(userTweets.get(userId));
        }
        
        // 2. Collect tweets from followees
        Set<Integer> followees = follows.getOrDefault(userId, new HashSet<>());
        for (int fid : followees) {
            if (fid == userId) continue;
            if (userTweets.containsKey(fid)) {
                feedHeap.addAll(userTweets.get(fid));
            }
        }
        
        // 3. Extract the 10 most recent
        List<Integer> result = new ArrayList<>();
        while (!feedHeap.isEmpty() && result.size() < 10) {
            result.add(feedHeap.poll().id);
        }
        return result;
    }

    public void follow(int followerId, int followeeId) {
        follows.computeIfAbsent(followerId, k -> new HashSet<>()).add(followeeId);
    }

    public void unfollow(int followerId, int followeeId) {
        if (follows.containsKey(followerId)) {
            follows.get(followerId).remove(followeeId);
        }
    }
}

Summary Table