[Leetcode] Find Median from Data Stream

A very intricate usage of heap.

Description

The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value and the median is the mean of the two middle values.

• For example, for arr = [2,3,4], the median is 3.
• For example, for arr = [2,3], the median is (2 + 3) / 2 = 2.5.

Implement the MedianFinder class:

• MedianFinder() initializes the MedianFinder object.
• void addNum(int num) adds the integer num from the data stream to the data structure.
• double findMedian() returns the median of all elements so far. Answers within 10-5 of the actual answer will be accepted.

Examples

Example 1:

Input
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
Output
[null, null, null, 1.5, null, 2.0]
Explanation
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // return 1.5 (i.e., (1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

Solution

If the array is sorted, median=the very middle elm when array has odd elms, and =average of middle two elms when array has even nums. That is to say, we can get median by spliting the array to smaller half and larger half. When array has odd elms, median = last of smaller half if smaller half has one more elm / top of larger half if larger half has one more elm. When array has even nums, median = (last of smaller half + top of larger half) / 2.

Now consider the assumption that the array is sorted. Actually, we don’t need a sorted array. We only need to preserve last of smaller half & top of larger half. Hence, heap suits the situation.

Keep a maxHeap storing the smaller half with it’s max at top (last of smaller half), and a minHeap storing the larger half with it’s min at top (top of larger half). Heap would update the max/min without sorting other elms and thus cost less memory. Number of elms in two heap should differ at most 1. Otherwise, they are not dividing the array by half, and requires reassignment. The longer one shall pop one elm out, and that elm would be pushed into the shorter one to make the dividing correctly again. Updating the len of heap may occur from min to max or max to min.

• code

ref: https://blog.csdn.net/qq_37821701/article/details/108289904