Solving Find Median from Data Stream: Continuous Median Calculation

The "Find Median from Data Stream" problem involves creating a data structure that can continuously provide the median of a dynamically changing set of numbers. This challenge tests the ability to efficiently insert numbers and calculate the median at any point.

Problem Statement

Design a data structure that supports the following two operations:

• void addNum(int num): Add a number to the data structure.
• double findMedian(): Return the median of all elements so far.

Example

• Operations: addNum(1), addNum(2), findMedian(), addNum(3), findMedian()
• Outputs: [null, null, 1.5, null, 2.0]

Solution Approach - Two Heaps

The solution utilizes two heaps (a max heap and a min heap) to maintain the elements in sorted order and allow for efficient median calculation.

MedianFinder {
  private maxHeap: Heap<number>;
  private minHeap: Heap<number>;

  constructor() {
    this.maxHeap = new Heap<number>((a, b) => b - a);
    this.minHeap = new Heap<number>((a, b) => a - b);
  }

  addNum(num: number): void {
    // Add to maxHeap if it's empty or the number is less than or equal to its top element
    if (this.maxHeap.isEmpty() || num <= this.maxHeap.peek()!) {
      this.maxHeap.insert(num);
    } else {
      this.minHeap.insert(num);
    }

    // Balancing the heaps: ensure maxHeap has the same or one more element than minHeap
    if (this.maxHeap.size() > this.minHeap.size() + 1) {
      this.minHeap.insert(this.maxHeap.extract()!);
    } else if (this.minHeap.size() > this.maxHeap.size()) {
      this.maxHeap.insert(this.minHeap.extract()!);
    }
  }

  findMedian(): number {
    if (this.maxHeap.size() === this.minHeap.size()) {
      // If both heaps have the same size, the median is the average of their tops
      return (this.maxHeap.peek()! + this.minHeap.peek()!) / 2;
    } else {
      // If maxHeap has more elements, the median is its top element
      return this.maxHeap.peek()!;
    }
  }
}

Breaking Down the Solution

The MedianFinder class is an elegant solution to the "Find Median from Data Stream" problem, utilizing two heaps—a max heap and a min heap. Here's a breakdown of how this solution works:

Class: MedianFinder

• Manages two heaps to store the lower and upper halves of the data stream.

Properties:

• maxHeap: A max heap (Heap<number>) to store the smaller half of the numbers. The top of this heap will always be the largest number of the lower half.
• minHeap: A min heap (Heap<number>) to store the larger half of the numbers. The top of this heap will always be the smallest number of the upper half.

Constructor:

• Initializes the two heaps. The max heap uses a comparator that favors larger values (b - a), and the min heap uses a comparator that favors smaller values (a - b).

Method: addNum(num: number)

• Inserts a new number into one of the two heaps.
• If the number is less than or equal to the top of the max heap, or if the max heap is empty, it's added to the max heap. Otherwise, it's added to the min heap.
• After insertion, the method checks and rebalances the heaps to ensure that their sizes differ by no more than one element. This rebalancing is crucial for the median calculation.

Method: findMedian(): number

• Returns the median of the current set of numbers.
• If the heaps are of equal size, the median is the average of the tops of the two heaps.
• If the heaps are of unequal size, the median is the top of the larger heap (which, in this implementation, is always the max heap).

How It Works:

• The max heap and min heap effectively split the data stream into two halves.
• By maintaining the size property (the max heap is always equal or one more than the min heap), the class can quickly calculate the median.
• When a new number is added, it's placed in the correct half of the data. If this insertion unbalances the heaps, the class moves the top element of the larger heap to the smaller heap.
• For finding the median, if the sizes are equal, the median is the average of the two middle numbers. If not, it's just the middle number (from the max heap).

This implementation is efficient and dynamic, making it well-suited for a situation where data is continuously streaming, and the median needs to be recalculated frequently.

Conclusion

The Find Median from Data Stream problem showcases the utility of heap data structures in maintaining a running median in an efficient and scalable way.