MedianHeap

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

public class MedianHeap {
	PriorityQueue <Integer> lower = null;  // max heap
	PriorityQueue <Integer> upper = null;  // min heap
	float median;

	public MedianHeap() {
		lower = new PriorityQueue <Integer>(16, new Comparator<Integer>() {
			@Override
			public int compare(Integer a, Integer b) {
				return b - a;
			}
		});
		upper = new PriorityQueue<Integer>();
		median = 0;
	}

	public void add(int i) {
		if (i > median) {
			upper.add(i);
			if (upper.size() - lower.size() > 1) {
				lower.add(upper.remove());
			}
		} else {
			lower.add(i);
			if (lower.size() - upper.size() > 1) {
				upper.add(lower.remove());
			}
		}

		if (lower.size() == upper.size()) {
			median = ((float)(lower.peek() + upper.peek())) / 2;
		} else if (lower.size() > upper.size()) {
			median = lower.peek();
		} else {
			median = upper.peek();
		}
	}

	public float getMedian() {
		return median;
	}

	public static void main(String []argv) {
		// random
		int []ary = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13};

		for (int i = 0; i < ary.length; i++) {
			int j = (int)Math.random()*(ary.length - i);
			int t = ary[i];
			ary[i] = ary[j];
			ary[j] = t;
		}

		//
		MedianHeap mh = new MedianHeap();

		for (int i: ary) {
			mh.add(i);
			System.out.println(mh.getMedian());
		}
	}
}