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

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

Design a data structure that supports the following two operations:

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

Example:

addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3) 
findMedian() -> 2

Follow up:

• If all integer numbers from the stream are between 0 and 100, how would you optimize it?
• If 99% of all integer numbers from the stream are between 0 and 100, how would you optimize it?

Solution

1. 用不同的 Data Structure，Time Complexity 的比较

   
   
   image.png

2. 如何能达到用Heap为O(1) ?

   • 维护两个堆，前半是max-heap, 后半是min-heap => median = (max of max-heap + min of min-heap) / 2.0. (必须是除以double数，否则java会把结果取为整数)
     1）Store the half greater numbers into a min-heap
     2）Store the half less number into a max-heap
     3）Get the median from the top of two heaps

3. 需要保证两个堆的SIZE：1) max == min 或者 2）max比min多一个值

   • 如何保证呢？
     1）轮流向max-heap, min-heap插值
     2）当size相当时，放max-heap
     3）否则，放min-heap

4. 但是，可能出现例外情况，需要进行调整 ：
   1） 当应该向max插值时，但是current value比较大，比min-heap的min还要大，说明其应该属于min-heap，但为了保证max和min的size：

    - min of min-heap ==> max-heap
    - current value ==> min-heap
   

   2） 当应该向min插值时，但是current value比较小，比max-heap的max还要小，说明其应该属于max-heap，但为了保证max和min的size：

     - max of max-heap ==> min-heap
     - current value ==> max-heap
   

Code

class MedianFinder {
    PriorityQueue <Integer> maxHeap;
    PriorityQueue <Integer> minHeap;

    /** initialize your data structure here. */
    public MedianFinder() {
        minHeap = new PriorityQueue <Integer> ();
        maxHeap = new PriorityQueue <Integer> (
            (int1, int2) -> int2 - int1
        );
    }
    
    public void addNum(int num) {
        // if size is identical, then insert into maxHeap
        // but might need to adjust
        
        if (maxHeap.size () == minHeap.size ()) {
            if (!minHeap.isEmpty () && num > minHeap.peek ()) {
                maxHeap.offer (minHeap.poll ());
                minHeap.offer (num);
            } else {
                maxHeap.offer (num);
            }
        } else if (maxHeap.size () > minHeap.size ()){
            if (!maxHeap.isEmpty () && num < maxHeap.peek ()) {
                minHeap.offer (maxHeap.poll ());
                maxHeap.offer (num);
            } else {
                minHeap.offer (num);
            }
        }
        
        // System.out.println ("min: " + Arrays.toString (minHeap.toArray()));
        // System.out.println ("max: " + Arrays.toString(maxHeap.toArray()));
    }
    
    public double findMedian() {
        if (maxHeap.size () == minHeap.size ()) {
            return (maxHeap.peek () + minHeap.peek ()) / 2.0;
        }

        return maxHeap.peek ();
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */