Median of Data Stream Using Two Heaps in DSA Typescript - Deep Dive

Overview - Median of Data Stream Using Two Heaps

What is it?

Median of Data Stream Using Two Heaps is a method to find the middle value of a continuously updating list of numbers. Instead of sorting the entire list every time a new number arrives, it uses two special containers called heaps to keep track of the smaller and larger halves of the numbers. This way, the median can be quickly found at any moment. It is useful when data comes in one by one and you want to know the middle value efficiently.

Why it matters

Without this method, finding the median in a growing list would require sorting the entire list every time a new number arrives, which is slow and inefficient. This would make real-time applications like live data analysis, stock price monitoring, or sensor data processing much slower and less responsive. Using two heaps solves this problem by keeping the data organized so the median can be found instantly, saving time and computing power.

Where it fits

Before learning this, you should understand basic data structures like arrays and heaps (priority queues). After this, you can explore more advanced streaming algorithms, order statistics, or balanced tree structures. This topic fits into the broader study of efficient data processing and real-time algorithms.

Mental Model

Core Idea

Keep the smaller half of numbers in one heap and the larger half in another heap so the median is always at the top of one or both heaps.

Think of it like...

Imagine you have two boxes: one holds all the smaller toys and the other holds all the bigger toys. By always balancing the number of toys in each box, you can quickly pick the middle-sized toy without sorting all toys every time you get a new one.

Max-Heap (smaller half)          Min-Heap (larger half)
┌───────────────┐               ┌───────────────┐
│      5        │               │      8        │
│    /   \      │               │    /   \      │
│   3     2     │               │   9     10    │
└───────────────┘               └───────────────┘

Median is either the top of max-heap (5) or average of tops (5 and 8)

Build-Up - 7 Steps

1

Foundation

Understanding Median Concept

Concept: Learn what median means in a list of numbers.

Median is the middle value when numbers are sorted. If the list has an odd number of elements, median is the middle one. If even, median is the average of the two middle numbers.

Result

Knowing how to find median by sorting helps understand why sorting every time is slow.

Understanding median as the middle value sets the goal for efficient data structures to find it quickly.

2

Foundation

Basics of Heaps (Priority Queues)

Concept: Learn what heaps are and how max-heap and min-heap work.

A max-heap always keeps the largest element at the top. A min-heap always keeps the smallest element at the top. Both allow quick access to these elements without sorting the entire list.

Result

You can quickly get the largest or smallest number from a heap in constant time.

Knowing heaps lets you organize data so you can quickly find important elements like max or min.

3

Intermediate

Splitting Data into Two Heaps

🤔Before reading on: do you think we should put all numbers in one heap or split into two heaps? Commit to your answer.

Concept: Divide numbers into two groups: smaller half in max-heap and larger half in min-heap.

When a new number arrives, compare it with the top of max-heap. If smaller or equal, add to max-heap; else add to min-heap. This keeps smaller numbers in max-heap and larger in min-heap.

Result

Two heaps hold the data split so the median is near the top of one or both heaps.

Splitting data this way keeps the middle values accessible without sorting all numbers.

4

Intermediate

Balancing the Two Heaps

🤔Before reading on: should the two heaps always have the same size or can they differ? Commit to your answer.

Concept: Keep the sizes of the two heaps balanced so their size difference is at most one.

After adding a number, if one heap has more than one extra element, move the top element from the bigger heap to the smaller heap. This keeps the heaps balanced.

Result

Balanced heaps ensure the median is always at the top of one or both heaps.

Balancing heaps is key to maintaining quick median access as data grows.

5

Intermediate

Calculating Median from Heaps

Concept: Find median based on the sizes of the two heaps.

If heaps are equal size, median is average of tops of both heaps. If one heap is bigger, median is the top of that heap.

Result

Median can be found in constant time without sorting all data.

Knowing how to get median from heaps completes the efficient median-finding process.

6

Advanced

Implementing Median Finder in TypeScript

🤔Before reading on: do you think we need to implement both max-heap and min-heap or can we use built-in structures? Commit to your answer.

Concept: Write code to maintain two heaps and find median as numbers stream in.

Use a max-heap for smaller half and min-heap for larger half. Insert numbers, balance heaps, and calculate median. TypeScript code uses classes and arrays to implement heaps.

Result

A working program that outputs median after each insertion.

Implementing the algorithm solidifies understanding and shows practical usage.

7

Expert

Handling Edge Cases and Performance

🤔Before reading on: do you think the algorithm handles duplicate numbers and large data streams efficiently? Commit to your answer.

Concept: Consider duplicates, large inputs, and performance trade-offs in real systems.

Duplicates are handled naturally by heaps. For very large streams, memory and heap operations remain efficient (logarithmic time). However, balancing and heap operations must be carefully implemented to avoid bugs.

Result

Robust median finder that works correctly and efficiently in real-world scenarios.

Understanding edge cases and performance ensures the algorithm is production-ready and reliable.

Under the Hood

Two heaps store the data split into smaller and larger halves. Max-heap keeps the largest of the smaller half at the top, min-heap keeps the smallest of the larger half at the top. Balancing ensures the heaps differ in size by at most one. Median is either the top of the bigger heap or average of both tops. Internally, heap operations like insert and extract run in logarithmic time, making the median calculation efficient even for large data streams.

Why designed this way?

Sorting the entire data stream every time is too slow. Using two heaps allows constant-time access to median candidates and logarithmic-time updates. This design balances speed and memory use. Alternatives like balanced trees exist but are more complex. Two heaps provide a simple, efficient, and practical solution.

Incoming Number
     │
     ▼
 ┌───────────────┐
 │ Compare with   │
 │ max-heap top   │
 └───────────────┘
     │
 ┌───┴────┐
 │        │
 ▼        ▼
Max-Heap  Min-Heap
 (smaller) (larger)
     │        │
     └───┬────┘
         ▼
   Balance Sizes
         │
         ▼
   Calculate Median
         │
         ▼
       Output

Myth Busters - 4 Common Misconceptions

Quick: Do you think the median is always the top of the max-heap? Commit to yes or no.

Common Belief: The median is always the top element of the max-heap.

Reality: The median can be the average of the tops of both heaps if they have equal size, or the top of the heap with one extra element.

Why it matters: Assuming median is always from one heap leads to incorrect median calculation when heaps are balanced.

Quick: Do you think heaps need to be perfectly balanced in size? Commit to yes or no.

Common Belief: Both heaps must always have exactly the same number of elements.

Reality: Heaps can differ in size by at most one element to allow for odd total counts.

Why it matters: Trying to keep heaps perfectly equal can cause unnecessary data moves and complexity.

Quick: Do you think duplicates break the two heaps median method? Commit to yes or no.

Common Belief: Duplicate numbers cause errors or incorrect medians in the two heaps method.

Reality: Duplicates are handled naturally by heaps without any special treatment.

Why it matters: Worrying about duplicates can lead to overcomplicated code or wrong assumptions.

Quick: Do you think sorting the entire data stream is faster than using two heaps? Commit to yes or no.

Common Belief: Sorting the entire list each time is just as fast or faster than using two heaps.

Reality: Sorting every time is much slower (O(n log n)) compared to two heaps (O(log n) per insertion).

Why it matters: Ignoring efficiency leads to slow programs that can't handle real-time data.

Expert Zone

1

The choice of max-heap and min-heap implementations affects performance; using binary heaps is common but Fibonacci heaps can optimize some operations.

2

Balancing heaps after every insertion is crucial; delaying balancing can cause incorrect median results.

3

In distributed systems, maintaining two heaps across nodes requires synchronization to keep median accurate.

When NOT to use

This method is not ideal when data is static or small, where simple sorting is faster. For very large data streams with memory constraints, approximate median algorithms like quantile sketches are better.

Production Patterns

Used in real-time analytics dashboards, financial tickers, sensor data monitoring, and anywhere median needs to be updated live without full data sorting.

Connections

Order Statistics

Builds-on

Understanding median as a special case of order statistics helps grasp how to find other ranked elements efficiently.

Balanced Binary Search Trees

Alternative approach

Balanced trees can also maintain median but are more complex; comparing them deepens understanding of data structure trade-offs.

Real-time Signal Processing

Application domain

Median filtering in signal processing uses similar concepts to smooth data streams, showing cross-domain algorithm reuse.

Common Pitfalls

#1 Not balancing heaps after insertion

Wrong approach:

Insert number into one heap and never move elements to balance sizes.

Correct approach:

After insertion, check sizes and move top element from bigger heap to smaller heap if size difference > 1.

Root cause:

Misunderstanding that heaps must be balanced to keep median calculation correct.

#2 Calculating median incorrectly when heaps are equal size

Wrong approach:

Return top of max-heap only when heaps are equal size.

Correct approach:

Return average of tops of max-heap and min-heap when heaps are equal size.

Root cause:

Assuming median is always from one heap without considering even number of elements.

#3 Using a min-heap for smaller half instead of max-heap

Wrong approach:

Store smaller half in min-heap and larger half in max-heap.

Correct approach:

Store smaller half in max-heap and larger half in min-heap.

Root cause:

Confusing which heap type keeps which half leads to wrong median calculation.

Key Takeaways

Median of a data stream can be found efficiently by splitting data into two heaps: max-heap for smaller half and min-heap for larger half.

Balancing the heaps so their sizes differ by at most one is essential to maintain correct median calculation.

Median is either the top of the bigger heap or the average of the tops when heaps are equal in size.

Using two heaps avoids sorting the entire data stream every time, making median calculation fast and suitable for real-time data.

Understanding heap operations and balancing is key to implementing a robust median finder.