Running median of an input stream - O(n*log(n))

medianHeap.java

import java.util.*;

class Main {
  private static class MedianHeap {
    PriorityQueue<Integer> lowers = new PriorityQueue<>(new Comparator<Integer>() {
      public int compare(Integer one, Integer two) {
        return -1 * one.compareTo(two);
      }
    });
    PriorityQueue<Integer> uppers = new PriorityQueue<>();
    
    public boolean add(int value) {
      boolean success = false;
      if (lowers.size() == 0 || value < lowers.peek()) {
        success = lowers.add(value);
      } else {
        success = uppers.add(value);
      }
      
      rebalance();
      return success;
    }
    
    public double median() {
      if (lowers.size() == uppers.size()) {
        return ((double) lowers.peek() + uppers.peek()) / 2;
      } else if (lowers.size() > uppers.size()) {
        return lowers.peek();
      } else {
        return uppers.peek();
      }
    }
    
    private void rebalance() {
      PriorityQueue<Integer> small = lowers.size() < uppers.size() ? lowers : uppers;
      PriorityQueue<Integer> large = lowers.size() < uppers.size() ? uppers : lowers;
      
      if (large.size() - small.size() > 1) {
        small.add(large.poll());
      }
    }
  }
  
  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    in.nextLine();
    
    MedianHeap medianHeap = new MedianHeap();
    while (in.hasNextInt()) {
      int input = in.nextInt();
      medianHeap.add(input);
      System.out.printf("%.1f%n", medianHeap.median());
    }
  }
}