Java algorithm to get the running median for an array of integer.

medianHeap.java

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {
        /**
        * The add number method
        */
        public static void addNumber(int num, PriorityQueue<Integer> lowers, PriorityQueue<Integer> highers) {
            if(lowers.size() == 0 || num < lowers.peek()) {
                lowers.add(num);
            } else {
                highers.add(num);
            }
        }
        /**
        * The rebalance method
        */
        public static void rebalance(PriorityQueue<Integer> lowers, PriorityQueue<Integer> highers) {
            PriorityQueue<Integer> biggerHeap = lowers.size() > highers.size() ? lowers : highers;
            PriorityQueue<Integer> smallerHeap = lowers.size() > highers.size() ? highers : lowers;
            if(biggerHeap.size() - smallerHeap.size() >= 2) {
                smallerHeap.add(biggerHeap.poll());
            }
        }
        /**
        * The get median method
        */
        public static double getMedian(PriorityQueue<Integer> lowers, PriorityQueue<Integer> highers) {
            PriorityQueue<Integer> biggerHeap = lowers.size() > highers.size() ? lowers : highers;
            PriorityQueue<Integer> smallerHeap = lowers.size() > highers.size() ? highers : lowers;
            if(biggerHeap.size() == smallerHeap.size()) {
                return ((double)biggerHeap.peek() + smallerHeap.peek())/2;
            } else {
                return biggerHeap.peek();
            }
        }
        /**
        * The get medians method 
        */
        public static double[] getMedians(int[] array) {
            PriorityQueue<Integer> lowHeap = new PriorityQueue<Integer>(new Comparator<Integer>(){
                public int compare(Integer a, Integer b) {
                    return -1 * a.compareTo(b);
                }
            });
            PriorityQueue<Integer> highHeap = new PriorityQueue<Integer>();
            double[] medians = new double[array.length];
            /**
            * The loop
            */
            for(int i=0; i < array.length; i++){
                int number = array[i];
                addNumber(number,lowHeap,highHeap);
                rebalance(lowHeap,highHeap);
                medians[i] = getMedian(lowHeap,highHeap);
                System.out.println(medians[i]);//this is the running median
            }
            return medians;
        }
        /**
        * The main
        */
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            int n = in.nextInt();
            int[] a = new int[n];
            for(int i=0; i < a.length; i++){
                a[i] = in.nextInt();
            }
            getMedians(a);
        }
}