Median of stream of integers

MedianOfIntegerStream.java

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

// Given a stream of unsorted integers, find the median element in sorted order at any given time.
// http://www.ardendertat.com/2011/11/03/programming-interview-questions-13-median-of-integer-stream/
public class MedianOfIntegerStream {

	public Queue<Integer> minHeap;
	public Queue<Integer> maxHeap;
	public int numOfElements;
	
	public MedianOfIntegerStream() {
		minHeap = new PriorityQueue<Integer>();
		maxHeap = new PriorityQueue<Integer>(10, new MaxHeapComparator()); 
		numOfElements = 0;
	}
	
	public void addNumberToStream(Integer num) {
		maxHeap.add(num);
		if (numOfElements%2 == 0) {
			if (minHeap.isEmpty()) {
				numOfElements++;
				return;
			}
			else if (maxHeap.peek() > minHeap.peek()) {
				Integer maxHeapRoot = maxHeap.poll();
				Integer minHeapRoot = minHeap.poll();
				maxHeap.add(minHeapRoot);
				minHeap.add(maxHeapRoot);
			} 
		} else {
			minHeap.add(maxHeap.poll());
		}
		numOfElements++;
	}
	
	public Double getMedian() {
		if (numOfElements%2 != 0)
			return new Double(maxHeap.peek());
		else
			return (maxHeap.peek() + minHeap.peek()) / 2.0; 
	}
	
	private class MaxHeapComparator implements Comparator<Integer> {
		@Override
		public int compare(Integer o1, Integer o2) {
			return o2 - o1;
		}
	}
	
	public static void main(String[] args) {
		MedianOfIntegerStream streamMedian = new MedianOfIntegerStream();
		
		streamMedian.addNumberToStream(1);
		System.out.println(streamMedian.getMedian()); // should be 1
		
		streamMedian.addNumberToStream(5);
		streamMedian.addNumberToStream(10);
		streamMedian.addNumberToStream(12);
		streamMedian.addNumberToStream(2);
		System.out.println(streamMedian.getMedian()); // should be 5
		
		streamMedian.addNumberToStream(3);
		streamMedian.addNumberToStream(8);
		streamMedian.addNumberToStream(9);
		System.out.println(streamMedian.getMedian()); // should be 6.5
	}
}

At line 15. Can you please explain why you have the number 10 in constructor ?

@karthikselva Because if you want to provide a custom comparator for the PriorityQueue, you also need to provide the initial capacity for it, so 10 is just a random number :)
See http://docs.oracle.com/javase/6/docs/api/java/util/PriorityQueue.html#PriorityQueue(int,%20java.util.Comparator).

Excellent implementation, thanks!

May you explain why a custom comparator is required? When I run the code after removing the custom comparator, I get incorrect results.

Thanks in advance.

The custom comparator is for changing the order of the heap. The default order is min. To convert to max heap, custom comparator is used.
http://docs.oracle.com/javase/6/docs/api/java/util/PriorityQueue.html#PriorityQueue(int,%20java.util.Comparator)

Thanks@Vedrana

Thank you for your excellent code. Could you please tell me if the capacity of max heap will change? Because if the capacity is set to be 10, and the number of numbers are bigger than 10. What will happen?

@bobzhang199102, from the PriorityQueue JavaDocs

A priority queue is unbounded, but has an internal capacity governing the size of an array used to store the elements on the queue. It is always at least as large as the queue size. As elements are added to a priority queue, its capacity grows automatically. The details of the growth policy are not specified.

I have added a removeNumberFromStream method, that removes the element if it is contained in either max or min heap. Then it checks if it needs to rebalance heap according to number of elements.

With Java 8:
https://docs.oracle.com/javase/8/docs/api/java/util/PriorityQueue.html

It doesn't require a initial size it seems.

Hi - is it possible to public this under an ASF 2.0 license?

This is much concise
https://www.programcreek.com/2015/01/leetcode-find-median-from-data-stream-java/