ReviseAlgo Logo

Heaps & Priority Queues

Top K Patterns & Running Median

Master Priority Queue patterns: Top K elements, K-way sorted merges, and the Two Heaps running median tracker.

Last Updated: August 2, 2026 • 20 min read

1. Introduction

What is the Top K Pattern?

The Top K Pattern uses a binary heap to track the K largest, smallest, or most frequent elements in a large dataset or dynamic data stream:
  • To track the K largest elements, use a Min-Heap of size K.
  • To track the K smallest elements, use a Max-Heap of size K.

    • Why is it Important?

    Sorting an array of size N to find the top K elements takes O(N log N) time. By maintaining a heap restricted to size K, we can process elements in O(N log K) time and O(K) auxiliary space. This is highly optimal when K \ll N.

    Where is it Used?

  • Streaming Metrics: Tracking the top 100 trending hashtags on social media feeds.
  • Running Statisticians: Calculating real-time medians for sensor data streams.

    • 2. Mental Models

    The Sieve (Top K Largest)

    Imagine a sifting sieve that only holds up to K stones:
  • The sieve acts as a Min-Heap. The smallest stone in the sieve sits at the top (the root).
  • If you find a new stone that is larger than the smallest stone in your sieve, you discard the smallest one, let it fall through, and place the new, larger stone inside.
  • Once you finish scanning all stones, the sieve contains the K largest stones.

    • The Seesaw (Running Median)

    Imagine balancing two groups of children on a seesaw:
  • Left Side (Max-Heap): Holds the smaller half of values. The largest value in this half sits at the top.
  • Right Side (Min-Heap): Holds the larger half of values. The smallest value in this half sits at the top.
  • By keeping the number of elements in both heaps balanced (size difference ≤ 1), the median is always right at the center seats!

    • 3. Core Algorithms & Implementations

    1. Top K Frequent Elements (LeetCode 347)

  • Count element frequencies using a HashMap.
  • Push entries into a Min-Heap of size K comparing by frequency.
  • If heap size exceeds K, pop the element with the lowest frequency.

    • 2. Find Median from Data Stream (LeetCode 295)

  • Store lower half of numbers in Max-Heap small, upper half in Min-Heap large.
  • Add number: push to small, pop largest from small and push to large.
  • Rebalance: If large.size() > small.size(), pop from large and push to small.
  • If sizes are equal, median is (small.peek() + large.peek()) / 2.0. Otherwise, it is small.peek().

    • 4. Visual Seesaw: Two Heaps Balancing Act

    Balancing numbers [5, 15, 1, 3] to find median:

    5. Real-World Examples

  • Search Query Autocomplete: Suggesting the top 10 most search-heavy queries starting with typed characters in real time.
  • Stock Index Medians: Yielding running mid-point values for stock market ticker feeds.

    • 6. Interview Perspective

    How Interviewers Ask This Topic

    Interviewers test heap sizing choices:
  • "Find the K-th largest element in an array." -> Use a Min-Heap of size K. Return heap.peek().
  • "Why use negative values in Python's heapq for max-heaps?" -> Python's heapq only implements min-heaps. Storing negated numbers (-val) reverses comparisons, simulating max-heap properties.

    • Common Mistakes

    Warning: 1. Wrong Heap Sizing: Storing all N elements inside a heap for K-largest queries. This takes O(N log N) time and O(N) space. Restricting size to K reduces bounds to O(N log K) time and O(K) space.
    > 2. Wrong Heap Choice: Using a Max-Heap to track K-largest elements. If you use a Max-Heap, you cannot pop the minimum elements, which forces you to store all N values.

    7. Summary

  • K-Largest: Min-Heap of size K. Evict roots that fall below thresholds.
  • K-Smallest: Max-Heap of size K. Evict roots that exceed thresholds.
  • Running Median: Pair a Max-Heap (lower half) and Min-Heap (upper half) keeping sizes balanced.

    • 8. Quiz

    Question 1: What is the time complexity to insert a new element into a priority queue of size K? Answer: O(log K) time.
    Question 2: In Python, if we push [10, 5, 20] into self.small as negated numbers, what is -self.small[0]? Answer: 20. The items stored are [-10, -5, -20]. The min-heap root index 0 holds the smallest value -20, which negates back to the maximum value 20.
    Question 3: How does a min-heap of size K find K largest elements instead of smallest? Answer: Because the root of the min-heap represents the smallest value currently in the top-K list. Any element larger than the root is guaranteed to be a candidate for the top-K, and we can safely pop the root (the minimum) to insert it.
    Question 4: True or False: If the two heaps in MedianFinder have sizes 4 and 4, the median is the average of both heap roots. Answer: True. The roots represent the maximum of the lower half and the minimum of the upper half, which are the two central elements of the sorted stream.
    Question 5: What is the time complexity to merge K sorted lists of total size N? Answer: O(N log K) time, since the priority queue size is restricted to K active list heads.