[20.9] Maintain Median value when new values are added

1. Example

 The default PriorityQueue is implemented with Min-Heap, that is the top element is the minimum one in the heap.
https://www.quora.com/How-do-I-calculate-the-median-of-given-sets-of-numbers-when-the-number-of-elements-in-a-list-are-changed

Example:
Starting configuration of heaps
Starting from the example you've considered, the heaps may look like this:
Left tree = max-heap, Right-tree = min-heap

Inserting an element in appropriate heap
Let's see, what happens if you get a new number, say 5:
Clearly, it's less than the root of max-heap, so we must insert it there.
Simply add it to the first available leaf in the tree.

Balancing the relevant heap
Now, successively swap until each parent is greater than its children (in case of min-heap, the condition is reversed; i.e. swap until each parent is smaller than its children)

Finding the median
Now, we see that difference in # of elements = 1, max-heap has more elements, therefore median = root of the max-heap = 6

Space-time complexity
For the heap approach, insertion and balancing takes O(log n). Looking up the median is O(1).

Below Value => max heap: 2,3,4,5(include median)
Above Value => min heap:6,10,11

A new value came in 
if larger than max heap => go to Above heap(min heap)
if smaller or equal to max heap => go to Below heap(max heap)
Odd number -> the size of below heap has one extra
Even number -> equal size on both heap


Get median => get max from max heap =>O(1)
Add number => heapify => O(logn) 

• A Comparator can be provided in the constructor when instantiating a PriorityQueue. Then the order of the items in the Queue will be decided based on the Comparator provided.
• If a Comparator is not provided, then the natural order (Comparable) of the Collection will be used to order the elements.

s={1,2,3,4,5} = > Median = 3
s= {1,2,3,4,5,6} => Median = (3+4)/2 = 3.5
s= {1,2,3,4,5,6,7}=>Median = 4

s= {4,5,6} = > Median =5
s=    {3,4,5,6}=>Median =4.5
s= {2,3,4,5,6,10}=> Median =4.5
s= {2,3,4,5,6,10,11}=> Median =5



Median = number of elements


2. Implementation
Q1: add a number larger than max
Q1: add a number smaller than min

// O(n) space, O(logn) time
public class Question9 {

  public static class MaxHeapComparator implements Comparator {
    public int compare(Integer first, Integer second) {
      return -first.compareTo(second);
    }
  }
  // max heap
  private PriorityQueue smallerHalf = new PriorityQueue(100, new MaxHeapComparator());
  // min heap
  private PriorityQueue largerHalf = new PriorityQueue();
  
  public void add(int newData) {

    largerHalf.add(newData);
    // always keep smallerHalf plus 1
    if (smallerHalf.size() < largerHalf.size()) {
      int elem = largerHalf.poll();
      smallerHalf.add(elem);
    }

  }

  public int median() {

     if ( smallerHalf.size() == 0  )
            return largerHalf.peek();
     else if ( largerHalf.size() == 0)
            return smallerHalf.peek();

    if (smallerHalf.size() + largerHalf.size() == 0) {
      return 0;
    }
    if (smallerHalf.size() == largerHalf.size()) { // even number
      return (smallerHalf.peek() + largerHalf.peek()) / 2;
    }
    return smallerHalf.peek(); // odd number, in add() always keep smallerHalf plus 1

  }

}

// Time:O(1) to get median, O(logn) to add a new number

private Comparator maxHeapComparator, minHeapComparator;
private PriorityQueue maxHeap, minHeap;

public void addNewNumber(int newNum)
{
       
      // Even
      if (maxHeap.size() == minHeap.size())
      {
           if ( minHeap.peek() != null && newNumber > minHeap.peek() )
           {
               // maintain maxHeap has one extra
               maxHeap.offer(minHeap.poll());
               minHeap.offer(newNumber);
           }
           else // if newNumber <= maxHeap.peek(), maxHeap suppose has one extra
           {
               maxHeap.offer(newNumber);
           }
      }
      // Odd( assume maxHeap has extra one)
      else 
      {
           // add to maxHeap, remove one to minHeap first
           if (  newNum < maxHeap.peek() )
           {
                  minHeap.offer( maxHeap.poll()  );
                  maxHeap.offer(  newNumber );
           }
           else 
           {
                  minHeap.offer(newNumber);
           }
      }
}



public static double getMedian ()
{



      if ( maxHeap.isEmpty()  )
            return minHeap.peek();
      else if ( minHeap.isEmpty() )
            return maxHeap.peek();
       


      if ( maxHeap.size() == minHeap.size() )
           return ( maxHeap.peek() + minHeap.peek() ) /2;
      else if ( maxHeap.size() > minHeap.size()  ) 
           return maxHeap.peek();
      else
           return minHeap.peek();

}

3. Similar Ones
http://javapapers.com/java/java-priorityqueue/
http://stackoverflow.com/questions/6065710/how-does-javas-priorityqueue-differ-from-a-min-heap-if-no-difference-then-why