Top-K Problems & Heap Applications

Imagine you're building a recommendation system for an e-commerce platform with 100 million products. A user searches for "wireless headphones," and your algorithm assigns a relevance score to each product. Now you need to display the top 10 most relevant results. How do you efficiently find these 10 products without sorting all 100 million items?

Or consider a real-time analytics dashboard that monitors server performance across 10,000 machines. You need to identify the 5 servers with the highest CPU usage to alert the operations team. The data changes every second—you can't afford to sort all 10,000 entries each time.

These are instances of the Top-K problem—one of the most ubiquitous patterns in software engineering. The naive approach (sort everything, take the first K) has O(n log n) time complexity. But with the right data structure—the heap—we can solve this in O(n log K) time, or even better in streaming scenarios.

The Top-K problem has a deceptively simple formulation:

Given a collection of n elements, find the K largest (or smallest) elements.

But this simple statement hides considerable depth. Let's formalize it precisely:

Formal Definition:

• Input: A collection A of n comparable elements and an integer K where 1 ≤ K ≤ n
• Output: A set S containing exactly K elements from A such that every element in S is greater than or equal to every element in A − S (for Top-K largest)

Key Observations:

1. Order within the K elements may or may not matter. Some problems ask for just the K elements (unordered), while others want them in sorted order. This affects the final step of your solution.

2. The Kth largest element has special significance. It serves as the "threshold"—any element greater than or equal to this value is in the Top-K set.

3. K is typically much smaller than n. Most real-world Top-K problems have K << n. If K approaches n, you're essentially sorting the entire collection.

4. The elements don't need to be distinct. Duplicates are handled naturally by the algorithms we'll explore.

Variants of the Top-K Problem:

Each variant uses the same fundamental heap-based approach, with slight modifications. Mastering the core pattern enables you to solve all variants.

The most intuitive approach to Top-K is simple: sort the collection, then take the first K elements. Let's analyze why this isn't optimal.

The Sorting Approach:

function topKBySorting(arr, k):
    sort(arr)  // O(n log n)
    return arr[0...k-1]  // O(k)

Time Complexity: O(n log n) — dominated by the sorting step Space Complexity: O(1) to O(n) depending on sorting algorithm

The Problem:

The sorting approach does far more work than necessary. Consider the search engine example with n = 100,000,000 products and K = 10:

• Sorting approach: ~2.66 billion comparisons (n log n ≈ 100M × 26.6)
• What we actually need: Information about just 10 elements

We're using a sledgehammer to hang a picture frame. Sorting computes the complete ordering of all elements when we only need the partial ordering—specifically, which elements are in the top K.

Alternative Approaches and Their Trade-offs:

For most practical scenarios, the heap-based approach provides the best balance:

• O(n log K) time complexity
• O(K) space complexity
• Works on streams (elements arriving one at a time)
• Simple to implement and understand
• Consistent performance (no worst-case degradation)

When K is very small (say, K ≤ 100) and n is very large, the heap approach is almost always the right choice.

Now we arrive at the heart of the Top-K pattern. The heap-based approach is elegant, efficient, and widely applicable. Here's the key insight:

To find the K largest elements, maintain a min-heap of size K. The smallest element in the heap is our "admission threshold"—any element larger must be in the Top-K.

Wait—a min-heap for finding the largest elements? This counterintuitive choice is precisely what makes the algorithm efficient. Let's break it down step by step.

The Algorithm:

function topKLargest(arr, k):
    minHeap = new MinHeap()
    
    for each element in arr:
        if minHeap.size() < k:
            // Phase 1: Fill the heap until we have K elements
            minHeap.insert(element)
        else if element > minHeap.peek():
            // Phase 2: New element beats our weakest candidate
            minHeap.extractMin()  // Remove weakest
            minHeap.insert(element)  // Add new champion
    
    return minHeap.elements()

Step-by-Step Trace:

Let's trace through finding the Top-3 from [5, 2, 9, 1, 7, 6, 8]:

Result: [7, 8, 9] — the three largest elements.

This is the most common point of confusion for engineers learning the Top-K pattern. Let's build a deep, intuitive understanding of why the heap choice seems "backwards."

The Insight: Gatekeeping, Not Championing

Think of the heap as a waiting room with limited capacity K. We want to keep the K strongest candidates inside.

The crucial question isn't "Who's the strongest?" but rather "Who should we kick out if someone better arrives?"

For this gatekeeping role, the heap root tells us:

• In a min-heap: Who is the weakest current occupant? (First to be evicted)
• In a max-heap: Who is the strongest current occupant? (Not useful for eviction)

When finding K largest elements, we need quick access to the weakest candidate—the one we'll evict when a better candidate arrives. That's what the min-heap root provides.

Worked Example: Why Max-Heap Fails

Suppose we incorrectly use a max-heap to find the Top-3 largest from [5, 2, 9, 1, 7]:

With a max-heap, every new element requires scanning the entire heap to find the minimum. For n elements, that's O(nK) total—worse than sorting when K is large!

With a min-heap, the minimum is always at the root—O(1) access, and O(log K) for the replacement. Total: O(n log K).

Let's rigorously analyze the time and space complexity of the heap-based Top-K algorithm.

Time Complexity: O(n log K)

Breaking down the operations:

1. For each of n elements:

   • Comparison with heap root: O(1)
   • If heap not full: Insert → O(log K)
   • If new element qualifies: Extract + Insert (or Replace) → O(log K)

2. Key insight: Heap size never exceeds K

   • All heap operations are O(log K), not O(log n)
   • This is the source of efficiency when K << n

3. Worst case: Every element triggers insertion

   • Happens when elements arrive in increasing order
   • Still O(n log K) because each insertion is O(log K)

4. Best case: After initial K elements, no replacements

   • Happens when K largest elements come first
   • O(K log K) for initial build + O(n - K) for comparisons
   • Effectively O(n) when K << n

Space Complexity: O(K)

The heap maintains exactly K elements at any time. This is crucial for:

• Memory-constrained environments: Can process billions of elements with tiny heap
• Stream processing: Never need to store the full input
• Distributed systems: Each node keeps local Top-K, merge at the end

Concrete Example:

• n = 1 billion elements (need ~8GB to store all)
• K = 100 (need ~800 bytes for heap)
• Memory reduction: 10,000,000x!

This space efficiency is what enables stream processing of massive datasets.

The basic Top-K pattern extends naturally to several common variations. Understanding these helps you recognize Top-K problems in different disguises.

Variation 1: Kth Largest Element (Single Element)

Sometimes you don't need all K elements—just the Kth one:

def kth_largest(arr, k):
    """The Kth largest is the root of the min-heap after processing."""
    min_heap = []
    for element in arr:
        heapq.heappush(min_heap, element)
        if len(min_heap) > k:
            heapq.heappop(min_heap)  # Evict smallest
    return min_heap[0]  # Root is Kth largest

The min-heap root IS the Kth largest—no additional work needed.

Variation 2: Top-K Frequent Elements

Instead of comparing by value, compare by frequency:

def top_k_frequent(arr, k):
    """Find K most frequently occurring elements."""
    # Step 1: Count frequencies - O(n)
    freq = Counter(arr)
    
    # Step 2: Use min-heap on frequencies - O(m log K) where m = unique elements
    min_heap = []  # (frequency, element)
    for element, count in freq.items():
        heapq.heappush(min_heap, (count, element))
        if len(min_heap) > k:
            heapq.heappop(min_heap)
    
    return [element for _, element in min_heap]

Variation 3: Top-K with Custom Comparator

Real-world objects have multiple attributes. Use a comparison key:

def top_k_products_by_rating(products, k):
    """Find K highest-rated products, breaking ties by price (lower wins)."""
    min_heap = []  # (rating, -price, product) - negate price for tie-breaking
    
    for product in products:
        key = (product.rating, -product.price, product)
        heapq.heappush(min_heap, key)
        if len(min_heap) > k:
            heapq.heappop(min_heap)
    
    return [item[2] for item in min_heap]

Variation 4: Top-K by Key/Score

Very common in recommendation systems and search engines:

def top_k_by_score(items: List[Tuple[str, float]], k: int) -> List[str]:
    """
    Given items with scores, return K items with highest scores.
    
    items: List of (item_id, score) tuples
    Returns: List of item_ids for Top-K items
    """
    min_heap = []  # (score, item_id)
    
    for item_id, score in items:
        if len(min_heap) < k:
            heapq.heappush(min_heap, (score, item_id))
        elif score > min_heap[0][0]:
            heapq.heapreplace(min_heap, (score, item_id))
    
    # Return in descending score order
    return [item_id for _, item_id in sorted(min_heap, reverse=True)]

This pattern appears in:

• Search result ranking
• Product recommendations
• Feed personalization
• Fraud score prioritization

The Top-K pattern is simple in concept but has several common implementation pitfalls. Being aware of these will save you debugging time.

We've explored the Top-K pattern in depth—one of the most practical applications of the heap data structure. Let's consolidate the key insights:

What's Next:

In the next page, we'll explore space-efficient K element tracking—how to maintain a Top-K set that can be dynamically updated as elements are added or removed, and techniques for reducing memory overhead even further.