2016-05-10 Running Medians

posted May 10, 2016, 8:41 AM by Samuel Konstantinovich   [ updated May 10, 2016, 8:41 AM ]
Senior Electives

public RunningMedian()  :
    Create an empty running median set.

public double getMedian() :
    When empty: throws new NoSuchElementException()
    Returns the median value

public void add(Integer x)
    add to the "SmallValue" heap if  x < median, 
    add to the "BigValue" heap otherwise. 
    balance the two heaps so that their size differ by no more than 1.