295. Find Median from Data Stream

Hard

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:

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

Solution:

use MinHeap and MaxHeap. Image MaxHeap is the left subtree of BST, and MinHeap is right subtree of BST.

If maxHeap and minHeap contains the same number of elements, the median is the average of the minHeap top and maxHeap top. otherwise we select median from the root of heap containing the more elements.

After adding the new element, the number of the elements in heap differ utmost by 1 elements.

Suppose maxHeap size is always larger than minHeap by 1 or the same as minHeap.

to balance the two heap, we try to add new element to minHeap(because maxHeap is larger).

1. add new element to maxHeap to get the largest element in maxHeap, which is to add into minHeap.

2. If minHeap size is larger than maxHeap, add minHeap root into maxHeap, in order to maintain maxHeap size is always maximum.

3. getMediam. use peek instead of poll

class MedianFinder {

    /** initialize your data structure here. */
    PriorityQueue<Integer> min = new PriorityQueue<Integer>();
    PriorityQueue<Integer> max = new PriorityQueue<Integer>(Collections.reverseOrder());
    public MedianFinder() {
        
    }
    
    public void addNum(int num) {
        max.add(num);
        min.add(max.poll());
        if(max.size() < min.size()){
            max.add(min.poll());
        }
    }
    
    public double findMedian() {
        if(max.size() == min.size()){
            return (max.peek() + min.peek())/2.0;
        }
        return max.peek();
    }
}

How to implement Heap in tree.(heap capacity is not fixed)

public class Node{

    public int val;

    public Node left,right,parent;

}

public class MyHeap{

    private Node head;

    private Node last;

    private Node size;

}

problem 1:

how to add a new node into the next of last?

how to pop the root, put the last element on the heap top, change the last variable of the heap?