Introduction

Finding the median in a static set of integers is straightforward: sort the numbers and pick the middle one. However, finding the median of a stream of data, where integers are constantly being added, is more challenging. This is because sorting the data on every addition is inefficient, especially with large streams. The aim is to maintain efficiency while accurately determining the median as each new integer is introduced.

The Median

The median is the middle value in a data set when the numbers are sorted in ascending order. For an odd number of elements, it's simply the central number. For an even number of elements, the median is the average of the two middle numbers.

Solution Overview

To solve the problem of finding the median from a stream of integers efficiently, a common approach is to use two heaps:

1. Max Heap: This heap contains the lower half of numbers.
2. Min Heap: This heap contains the upper half of numbers.

Key Operations:

• Insertion: Add each incoming integer to one of the heaps.
• Balance: Ensure the heaps are balanced, i.e., their sizes differ by at most one.
• Retrieval: The median is determined based on the sizes of the heaps.

Algorithm

Steps

1. Insert an element:
   • If the number is less than or equal to the maximum of the max heap, insert it into the max heap.
   • Otherwise, insert it into the min heap.
2. Balance the heaps:
   • If the max heap has more than one extra element compared to the min heap, move the root of the max heap to the min heap.
   • If the min heap has more elements than the max heap, move the root of the min heap to the max heap.
3. Find the median:
   • If both heaps are of equal size, the median is the mean of the root elements of both heaps.
   • If one heap has an extra element, the median is the root of that heap.

Example

Consider a stream of integers: 5, 15, 1, 3.

• Insert 5:
  Max Heap = [5]
  Min Heap = []
• Insert 15:
  Max Heap = [5]
  Min Heap = [15]
• Insert 1:
  Max Heap = [1, 5]
  Min Heap = [15]
• Insert 3:
  Max Heap = [1, 3]
  Min Heap = [5, 15]

The heaps balance, leading to a median of 4 (the average of 3 and 5).

Complexity

• Time Complexity:
  Each insertion and balancing operation is O(log n), where n is the number of elements. Therefore, the overall time complexity for finding the median in the stream is efficient for real-time processing.
• Space Complexity:
  Since we are storing all elements in the heaps, the space complexity is O(n).

Pseudocode

1function addElement(num):
2    if maxHeap is empty or num <= maxHeap.top():
3        maxHeap.insert(num)
4    else:
5        minHeap.insert(num)
6    
7    if maxHeap.size() > minHeap.size() + 1:
8        minHeap.insert(maxHeap.extractTop())
9    elif minHeap.size() > maxHeap.size():
10        maxHeap.insert(minHeap.extractTop())
11
12function findMedian():
13    if maxHeap.size() > minHeap.size():
14        return maxHeap.top()
15    else:
16        return (maxHeap.top() + minHeap.top()) / 2

Summary

Conclusion

The problem of finding a running median from a stream of numbers is significant in scenarios ranging from financial data analysis to real-time monitoring systems. The described dual-heap solution provides efficient and precise medians, highlighting the power of data structures in computational problems. By understanding and implementing such solutions, developers can effectively manage continuous data streams and derive insightful results seamlessly.