public class MedianFinder {

    // elements higher than the median go into this queue... but
    PriorityQueue<Integer> _maxQueue = new PriorityQueue<Integer>(10, new Comparator<Integer>() {

            @Override
            public int compare(Integer a, Integer b) {
                return a - b;
            }

        });
    PriorityQueue<Integer> _minQueue = new PriorityQueue<Integer>(10, new Comparator<Integer>() {

            @Override
            public int compare(Integer a, Integer b) {
                return b - a;
            }

        });


    // Adds a number into the data structure.
    public void addNum(int num) {
        if (_maxQueue.isEmpty() && _minQueue.isEmpty()) {
            _minQueue.offer(num);
            return;
        }

        double currMedian = findMedian();

        if ((double)num > currMedian) {
            if (_maxQueue.size() > _minQueue.size()) {
                _minQueue.offer(_maxQueue.poll());
            }

            _maxQueue.offer(num);
        } else {
            if (_minQueue.size() > _maxQueue.size()) {
                _maxQueue.offer(_minQueue.poll());
            }

            _minQueue.offer(num);
        }
    }

    // Returns the median of current data stream
    public double findMedian() {
        if (_maxQueue.isEmpty()) {
            return (double)_minQueue.peek();
        } else if (_minQueue.isEmpty()) {
            return (double)_maxQueue.peek();
        } else {
            if ((_maxQueue.size() + _minQueue.size()) % 2 == 0) {
                return (double)(_maxQueue.peek() + _minQueue.peek()) / 2;
            }
            return _maxQueue.size() > _minQueue.size() ? _maxQueue.peek() : _minQueue.peek();
        }
    }
};

// Your MedianFinder object will be instantiated and called as such:
// MedianFinder mf = new MedianFinder();
// mf.addNum(1);
// mf.findMedian();