Compute the median of online data - EPI

Compute the median of online data

OnlineMedian.java

	private static List<Double> globalResult = new ArrayList<>();
	// @include
	public static void onlineMedian(InputStream sequence) {
	// minHeap stores the larger half seen so far.
	PriorityQueue<Integer> minHeap = new PriorityQueue<>();
	// maxHeap stores the smaller half seen so far.
	PriorityQueue<Integer> maxHeap =
	new PriorityQueue<>(11, Collections.reverseOrder());
	Scanner s = new Scanner(sequence);
	while (s.hasNextInt()) {
	int x = s.nextInt();
	if (minHeap.isEmpty()) {
	// This is the very first element.
	minHeap.add(x);
	} else {
	if (x >= minHeap.peek()) {
	minHeap.add(x);
	} else {
	maxHeap.add(x);
	}
	}
	// Ensure minHeap and maxHeap have equal number of elements if
	// an even number of elements is read; otherwise, minHeap must have
	// one more element than maxHeap.
	if (minHeap.size() > maxHeap.size() + 1) {
	maxHeap.add(minHeap.remove());
	} else if (maxHeap.size() > minHeap.size()) {
	minHeap.add(maxHeap.remove());
	}
	// @exclude
	globalResult.add((minHeap.size() == maxHeap.size()
	? 0.5 * (minHeap.peek() + maxHeap.peek())
	: minHeap.peek()));
	// @include
	System.out.println(minHeap.size() == maxHeap.size()
	? 0.5 * (minHeap.peek() + maxHeap.peek())
	: minHeap.peek());
	}
	}

http://blog.csdn.net/fightforyourdream/article/details/17300465

    private static Comparator<Integer> maxHeapComparator;
    private static Comparator<Integer> minHeapComparator;
    private static PriorityQueue<Integer> maxHeap;  // 大堆里放小于中位数的元素
    private static PriorityQueue<Integer> minHeap;  // 小堆里放大于中位数的元素

    // O(logn)
 public static void addNewNumber(int randomNumber) {
            /* Note: addNewNumber maintains a condition that maxHeap.size() >= minHeap.size() */
            if (maxHeap.size() == minHeap.size()) {

  // 当小堆size与大堆相等时，中位数等于(maxHeap.top()+minHeap.top())/2
                if ((minHeap.peek() != null) && randomNumber > minHeap.peek()) {

  // 新数比中位数大，所以要放入小堆，但因为大堆的size必须大等于小堆
                    maxHeap.offer(minHeap.poll());

   // 所以要先把小堆中最小的元素移到大堆中
                    minHeap.offer(randomNumber);

   // 然后再把新数放入小堆
                } else {

   // 新数比中位数小或相等，所以放大堆
                    maxHeap.offer(randomNumber);
                }
            }
            else {

   // 这种情况必定是大堆的size比小堆多1，则中位数等于maxHeap.top()
                if(randomNumber < maxHeap.peek()){

  // 新数比中位数小或相等，所以放大堆
                    minHeap.offer(maxHeap.poll());

   // 先把大堆的最大元素转移到小堆
                    maxHeap.offer(randomNumber);

   // 然后把新数放入大堆
                }
                else {

 // 新数比中位数大，所以放小堆，因为现在大堆的size比小堆多1，所以可以直接放入小堆，无需转移
                    minHeap.offer(randomNumber);
                }
            }
    }
 // O(1)
    public static double getMedian() {
            /* maxHeap is always at least as big as minHeap. So if maxHeap is empty, then minHeap is also. */                
            if (maxHeap.isEmpty()) {
                return 0;
            }
            if (maxHeap.size() == minHeap.size()) {

  // 当大小堆size相同时，取平均
                return ((double)minHeap.peek() + (double) maxHeap.peek()) / 2;
            } else {

   // 否则大堆size比小堆多1，因此中位数就是大堆的最大值
                /* If maxHeap and minHeap are of different sizes, then maxHeap must have one extra element. Return maxHeap’s top element.*/                        
                return maxHeap.peek();
            } 
    }

Also check http://www.hawstein.com/posts/20.9.html