LESSON 52 · ADVANCED4 min read

Dual-Heap Architectures: Continuous Median Finding and Top-K Streaming

Architect high-performance streaming analytics using dual-heap balancing for continuous median calculation and bounded PriorityQueues for Top-K tracking.

OpenJDK 21+ (LTS)Free to readModule 13 of 15

YOUR NEXT SMALL WINS

By the end, you’ll be able to…

Balance dual max-heap and min-heap structures to query the continuous median of a data stream in O(1)
Maintain bounded min-heaps to track Top-K frequent elements in streaming time
Analyze heap resizing and comparator allocation costs in high-frequency data pipelines

01The Problem of Continuous Median Streaming

Calculating the median of an unchanging array is simple: sort the array in O(n log n) and inspect the middle element. However, in continuous real-time streams—such as financial market tick feeds, sensor networks, or server latency monitoring—data arrives sequentially.

Re-sorting an array of n numbers on every arrival requires O(n log n), or O(n) using insertion into a sorted list. Over n elements, this degrades total processing time to O(n^2)—completely unacceptable for high-throughput streaming systems.

The optimal solution uses a Dual-Heap architecture: partitioning incoming numbers into two halves: a Max-Heap for the smaller half of numbers, and a Min-Heap for the larger half of numbers.

02Dual-Heap Invariant and Median Extraction

Let maxHeap store the lower half of values (its top is the largest of the lower half), and minHeap store the upper half (its top is the smallest of the upper half).

We maintain two fundamental invariants: 1. Ordering: Every element in maxHeap <= every element in minHeap (maxHeap.peek() <= minHeap.peek()). 2. Size Balance: The size of maxHeap is either equal to minHeap, or exactly 1 element larger (maxHeap.size() == minHeap.size() or maxHeap.size() == minHeap.size() + 1).

Finding the median becomes a strict O(1) query: If maxHeap has more elements, the median is maxHeap.peek(). If both heaps have equal size, the median is the average of maxHeap.peek() and minHeap.peek(). Adding a number takes O(log n) heap insertion time.

example.js☕Java

Ctrl + ↵

import java.util.Collections;
import java.util.PriorityQueue;

public class MedianFinder {
    private final PriorityQueue<Integer> maxHeap; // Lower half
    private final PriorityQueue<Integer> minHeap; // Upper half

public MedianFinder() {
        // Max-heap for lower half, Min-heap for upper half
        this.maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        this.minHeap = new PriorityQueue<>();
    }

public void addNum(int num) {
        // 1. Add to maxHeap first
        maxHeap.offer(num);

// 2. Enforce ordering invariant: maxHeap top <= minHeap top
        minHeap.offer(maxHeap.poll());

// 3. Enforce size balance invariant: maxHeap can hold at most 1 more than minHeap
        if (maxHeap.size() < minHeap.size()) {
            maxHeap.offer(minHeap.poll());
        }
    }

public double findMedian() {
        if (maxHeap.size() > minHeap.size()) {
            return maxHeap.peek();
        }
        return (maxHeap.peek() + minHeap.peek()) / 2.0;
    }
}

Output

Click Run or press Ctrl+Enter

Output will appear here after you run the code.

03Tracking Top-K Frequent Elements in Streaming Pipelines

Another classic streaming requirement is reporting the Top-K most frequent items (e.g., trending search queries or top error codes). A frequency map tracks counts in O(1). To extract the top k items, storing all unique items in a max-heap requires O(m log m) where m is unique elements.

By using a bounded Min-Heap of size k, we achieve superior O(m log k) runtime. When inserting an element: if heap size < k, insert it. If the heap is full and the new element's frequency exceeds heap.peek(), evict the min element and insert the new one.

At the end of processing, the heap contains the exact top k highest-frequency items in O(m log k) time and O(k) auxiliary memory.

04Streaming Algorithm Comparison Table

Comparing data structures for streaming median and Top-K analytics across time and space metrics:

The Dual-Heap structure delivers the gold standard: O(1) query latency and O(log n) incremental update cost.

notes.txtPlain text

+----------------------+-------------------+-------------------+-------------------+| Architecture         | Add Element Time  | Query Median Time | Space Complexity  |+----------------------+-------------------+-------------------+-------------------+| Sorted Array List    | O(n) insertion    | O(1) index        | O(n)              || Resorted Array       | O(n log n) sort   | O(1) index        | O(n)              || Dual-Heap (Optimal)  | O(log n) heap push| O(1) heap peek    | O(n)              || Top-K Bounded Heap   | O(log k)          | O(k log k) extract| O(k)              |+----------------------+-------------------+-------------------+-------------------+

LET IT CLICK

The ideas worth keeping.

Dual-heap balancing enables O(1) continuous median queries and O(log n) insertions.
Bounded min-heaps track top-k elements in O(m log k) time while bounding auxiliary memory to O(k).
Dual-heaps maintain ordering (maxHeap <= minHeap) and size balance (|diff| <= 1).

TURN UNDERSTANDING INTO SOMETHING YOU CAN DO

Make it yours.

Type and test your code right here in the interactive workspace. Run your solution, check the output, and compare with the worked guide when ready.

Exercise 1: Trace the sizes and contents of maxHeap and m

Trace the sizes and contents of maxHeap and minHeap after adding numbers 5, 15, 1, 3 to an initially empty MedianFinder.

your_turn_1.java☕Java

Ctrl + ↵

Output

Click Run or press Ctrl+Enter

Output will appear here after you run the code.

Explore a worked solution

one_possible_solution.javaJava

// Add 5: maxHeap=[5], minHeap=[] -> Median = 5.0// Add 15: maxHeap=[5], minHeap=[15] -> Median = (5+15)/2 = 10.0// Add 1: maxHeap=[5, 1], minHeap=[15] -> Median = 5.0// Add 3: maxHeap=[3, 1], minHeap=[5, 15] -> Median = (3+5)/2 = 4.0

Follow the 3-step invariant: push to maxHeap, transfer to minHeap, rebalance size if needed.

Exercise 2: Why is a Min Heap of size k used to find Top

Why is a Min-Heap of size k used to find Top-K largest elements, rather than a Max-Heap?

your_turn_2.java☕Java

Ctrl + ↵

Output

Click Run or press Ctrl+Enter

Output will appear here after you run the code.

Explore a worked solution

one_possible_solution.javaJava

// A Min-Heap of size k keeps the current k largest elements seen so far.// The root (peek()) is the smallest of these top k elements.// When a new element arrives, we only need to compare it with the root:// if it is larger than root, we evict root and insert the new element.// This limits memory to O(k) and each comparison/insert to O(log k) rather than O(log n).

What element does the root of a Min-Heap expose?

Keep exploring.

The official references behind this lesson, when you want a second angle or the full details.

MODULE 13 · PRACTICAL SELF-CHECK

Pause. Put the pieces together.

You’ve reached the end of BST, Min/Max Heaps & Priority Queues. Before moving on, use this task to check what you can do independently.

Implement continuous median streaming and Top-K frequency tracking using PriorityQueues.

Try it in your own environment and write down the result. This is a self-check; reading completion does not evaluate your code.

Review this module

One lesson closer.

Reading is a start. Trying it yourself makes the connection.

Solve the hands-on coding challenge in the knowledge section to verify your code and unlock lesson completion.

By the end, you’ll be able to…

01The Problem of Continuous Median Streaming

02Dual-Heap Invariant and Median Extraction

03Tracking Top-K Frequent Elements in Streaming Pipelines

04Streaming Algorithm Comparison Table

The ideas worth keeping.

Make it yours.

Exercise 1: Trace the sizes and contents of maxHeap and m

Exercise 2: Why is a Min Heap of size k used to find Top

What stayed with you?

Exercise 1: Trace the sizes and contents of maxHeap and m

Keep exploring.

Pause. Put the pieces together.

One lesson closer.