Median from Data Stream

Design a data structure that supports the following two operations:

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

Example :

addNumber(1)

addNumber(2)

findMedian() -> 1.5

addNumber(3) 

findMedian() -> 2

Discussion - 

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.

We can use heap data structure to solve this problem. We can use two heaps to store the lower half and the higher half of the data stream. The size of the two heaps differs at most 1

We will maintain two heaps in the following way:

• A max-heap to store the smaller half of the input numbers
• A min-heap to store the larger half of the input numbers

This gives access to median values in the input: they comprise the top of the heaps!

Java Code - 

class Median {
    PriorityQueue<Integer> minHeap = null;
    PriorityQueue<Integer> maxHeap = null;
 
    public Median() {
        minHeap = new PriorityQueue<>();
        maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
    }
 
    public void addNumber(int k) {
        minHeap.offer(k);
        maxHeap.offer(minHeap.poll());
 
        if(minHeap.size()<maxHeap.size()){
            minHeap.offer(maxHeap.poll());
        }
    }
 
    public double findMedian() {
        if(minHeap.size() > maxHeap.size()){
            return minHeap.peek();
        }else {
            return (minHeap.peek()+maxHeap.peek())/2.0;
        }
    }
}

Time Complexity - O(log(n))