Find Median from Data Stream

Background Knowledge

The problem of finding the median from a data stream is a classic example of an online algorithm, where we need to process the data in a sequential manner and make decisions based on the current state of the system. To solve this problem efficiently, we need to understand the concept of heaps and priority queues. A heap is a specialized tree-based data structure that satisfies the heap property: the parent node is either greater than (or less than) its child nodes. This property allows us to efficiently extract the minimum or maximum element from the heap.

The median of a dataset is the middle value when the data is sorted in ascending order. If the dataset has an even number of elements, the median is the average of the two middle values. To find the median efficiently, we can use two heaps: a max heap to store the smaller half of the numbers and a min heap to store the larger half. By maintaining the balance between the two heaps, we can ensure that the median is always accessible in constant time.

The key concept here is to understand how to maintain the balance between the two heaps. We need to ensure that the size of the max heap is always greater than or equal to the size of the min heap, and the maximum element in the max heap is less than or equal to the minimum element in the min heap. This balance is crucial in maintaining the correctness of the median calculation.

Algorithm/Approach

The general approach to solve this problem is to use a combination of heaps and priority queues to maintain the balance between the smaller and larger halves of the numbers. We can use the following algorithm pattern:

• Use two heaps: a max heap and a min heap
• When adding a new number, determine which heap to add it to based on the current state of the heaps
• After adding the number, rebalance the heaps to maintain the correct balance
• When finding the median, use the top elements of the two heaps to calculate the median

Step-by-Step Strategy

To implement the solution, follow these steps:

1. Initialize two empty heaps: a max heap and a min heap
2. When adding a new number, compare it with the top element of the max heap (if it exists)
3. If the new number is less than or equal to the top element of the max heap, add it to the max heap
4. Otherwise, add it to the min heap
5. After adding the number, check if the max heap has more than one more element than the min heap
6. If so, remove the top element from the max heap and add it to the min heap
7. When finding the median, check if the total number of elements is odd or even
8. If it's odd, the median is the top element of the max heap
9. If it's even, the median is the average of the top elements of the max heap and the min heap

Common Pitfalls

When implementing the solution, watch out for the following common pitfalls:

• Not maintaining the correct balance between the two heaps
• Not handling the case where the total number of elements is odd or even correctly
• Not using the correct data structure (e.g., using a single heap instead of two)

Time & Space Complexity

The expected time complexity for adding a number is $O(\log n)$, where $n$ is the total number of elements. The expected time complexity for finding the median is $O(1)$. The space complexity is $O(n)$, where $n$ is the total number of elements.