Top K Elements Pattern: Find the Best K Without Sorting Everything

Scenario context

To find the top K largest elements, maintain a min-heap of size K. For every new element, push it onto the heap. If the heap exceeds K, evict the minimum. After processing all N elements, the heap holds exactly the K largest. O(N log K) time — orders of magnitude faster than sorting when K is small.

Twitter needs to show the top 10 trending hashtags from 50 million tweets in real time. Sorting all 50 milli…

This walkthrough focuses on The 50-Million-Tweet Problem: Why You Cannot Sort Everything.

Before making a design choice, clarify:

• Twitter needs to show the top 10 trending hashtags from 50 million tweets in real time.
• Sorting all 50 million records to find the top 10 would take O(N log N) — roughly 50M × 25 = 1.25 billion operations.
• For a system processing new tweets every millisecond, this is unacceptable.

Concepts in play: tree-data-structures, jvm-internals-and-garbage-collection, database-indexing, core-algorithm-patterns

Stage 1 — Min-Heap of Size K: The Eviction Strategy That Finds the Top K

• The strategy sounds counterintuitive: to find the K largest elements, you use a min-heap .
• A min-heap of size K holds the K largest elements seen so far.
• Its root is the smallest of those K elements — the weakest member of your current top-K leaderboard.
• When a new element arrives: - If it is larger than the root , it can displace the weakest champion.

Observable outcome: When a new element arrives: - If it is larger than the root , it can displace the weakest champion.

Stage 2 — Min-Heap for Top K Largest, Max-Heap for Top K Smallest

• The core algorithm in three lines of logic: After the loop, heap holds the answer.
• Worked example — top 3 largest from [3, 1, 5, 12, 2, 11, 7]: Result: top 3 largest = {7, 11, 12}.
• The heap never grew beyond K = 3.
• In Java: No comparator needed for top-K-largest — the default min-heap is exactly what you want.

for each element x in the collection:
    heap.offer(x)
    if heap.size() > K:
        heap.poll()   // evict the "weakest" candidate

PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // default: min-heap

Observable outcome: In Java: No comparator needed for top-K-largest — the default min-heap is exactly what you want.

Stage 3 — Deep Dive: How PriorityQueue Handles K-Bounded Heap Operations

• Internals: Heap Sift-Up, Sift-Down, and the Eviction Trigger Java's PriorityQueue is a binary heap in an array .
• The key invariant: every node is less than or equal to its children.
• The root (index 0) is always the minimum — accessible in O(1) via peek() .
• offer(x) places the new element at the array's tail (index size ) and sifts up : it compares the element to its parent at (i-1)/2 and swaps if necessary, repeating until the heap property is satisfied.

Observable outcome: offer(x) places the new element at the array's tail (index size ) and sifts up : it compares the element to its parent at (i-1)/2 and swaps if necessary, repeating until the heap property is satisfied.

Stage 4 — Visualizing Heap Eviction as Elements Arrive

• The flowchart below shows the per-element decision loop, including the eviction trigger that keeps the heap bounded at K: After the main loop, draining the heap gives the K elements in ascending order.
• If you need descending order (largest first), drain into an array and reverse, or use Collections.reverseOrder() on a second pass.

flowchart TD
    A([Next element x]) --> B[heap.offer x]
    B --> C{heap.size > K?}
    C -- Yes --> D[heap.poll  evict minimum]
    C -- No --> E{More elements?}
    D --> E
    E -- Yes --> A
    E -- No --> F[heap contains top K elements]
    F --> G{Need K elements in order?}
    G -- Yes --> H[Drain heap into array  O K log K]
    G -- No --> I[Return heap directly]

Observable outcome: If you need descending order (largest first), drain into an array and reverse, or use Collections.reverseOrder() on a second pass.

Stage 5 — Real-World Applications: Trending Hashtags, Recommendations, and Monitoring

• Social media trending — Twitter and TikTok compute top-K hashtags or topics from a sliding window of recent activity.
• A frequency map builds the counts; a min-heap of size K runs over the map entries.
• The entire pipeline fits in a single O(N log K) pass, meaning trending can refresh every few seconds even at billions of events per day.
• Recommendation engines — Spotify's "Daily Mix" selects the K most relevant tracks from a catalog of 100 million songs.

Observable outcome: Recommendation engines — Spotify's "Daily Mix" selects the K most relevant tracks from a catalog of 100 million songs.

Stage 6 — Java PriorityQueue and Guava's MinMaxPriorityQueue in Practice

• Java's PriorityQueue is the idiomatic choice and sufficient for all four problems above.
• Two limitations worth knowing: 1.
• PriorityQueue is not thread-safe .
• For concurrent stream processing, use java.util.concurrent.PriorityBlockingQueue or externally synchronize.

// Guava dependency: com.google.guava:guava
import com.google.common.collect.MinMaxPriorityQueue;

MinMaxPriorityQueue<Integer> deque = MinMaxPriorityQueue
        .maximumSize(k)   // automatically evicts the minimum when size exceeds K
        .create();

deque.add(5);
deque.add(1);
deque.add(10);
// deque.peekLast() = minimum; deque.peekFirst() = maximum

Observable outcome: For concurrent stream processing, use java.util.concurrent.PriorityBlockingQueue or externally synchronize.

End-to-end outcome

After working through the stages, you should be able to explain:

• Using the wrong heap direction.
• This is the 1 interview mistake.
• • Core idea: A min-heap of size K acts as a rolling leaderboard — every new element challenges the weakest current champion.
• If it wins, the champion is evicted.

Alternatives considered

Decision Guide: When to Use a Heap vs QuickSelect

Decision Guide: When to Use a Heap vs QuickSelect

Failure and degraded modes

Trade-offs: Heap vs Sort vs QuickSelect

• Detection: Understanding when to use each approach is as important as knowing how to implement them: The heap is the right default choice for interviews and production systems where K ≪ N, data may arrive in a…
• User or operator impact: Understanding when to use each approach is as important as knowing how to implement them: The heap is the right default choice for interviews and production systems where K ≪ N, data may arrive in a…