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.

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.

Rust Solution

Rust's BinaryHeap is a max-heap out of the box, so max_heap needs no comparator; the min_heap is turned into a min-heap by storing Reverse<i32>, wrapping each value as Reverse(num) on push and destructuring it back with let Reverse(v) = ... on pop. Both peek() and pop() return an Option, so every access ends in .unwrap(), and since peek() hands back a &i32 borrow it is dereferenced with * before the as f64 cast in find_median. The &mut self on add_num versus &self on find_median encodes in the signature that only insertion mutates the heaps.

Go Solution

Go's container/heap supplies only the algorithm, so each of MaxHeap and MinHeap is a plain []int that must implement Len/Less/Swap/Push/Pop to satisfy heap.Interface; the sole difference between them is the Less comparison (h[i] > h[j] versus h[i] < h[j]), because the package is a min-heap by default. Mutation routes through the free functions heap.Push(m.maxH, num) and heap.Pop(m.maxH) rather than the methods directly, which is why Push/Pop traffic in interface{} and recover the value with the x.(int) type assertion, append to grow, and the old[:n-1] reslice to shrink. Peeking is a manual (*m.maxH)[0] since the heap exposes no top accessor, and the pointer receivers (*MaxHeap) are required so Push/Pop can rewrite the slice header in place.