Just Programming...: Interviewstreet Median Challenge Part 2 Solution C++

The median of M numbers is defined as the middle number after sorting them in order, if M is odd or the average number of the middle 2 numbers (again after sorting) if M is even. Given an empty number list at first. Then you can add or remove some number from the list. For each add or remove operation, output the median of numbers in the list.
1) Use two multisets - first one will keep small n/2 numbers, minset and other one will keep next n/2 numbers, maxset.
2) For insert operation:
     if the number is greater than max of minset, add it to maxset
     else add it to minset
3) For remove operation:
     if the number is in minset, remove it
     else if number is in maxset, remove it
     else do nothing
4) After every insert/remove operation, adjust size of both sets i.e. make it n/2
     if(size-of-maxset > size-of-minset) remove first element from maxset and insert it in minset
     if(size-of-minset > size-of-maxset + 1) remove last element from minset and insert it in maxset
5) Calculate Median as..
     if(size of both minset and maxset is zero) No median
     else if (size of minset > size of maxset) max of minset is median
     else if (size of minset = size of maxset) avg of max of minset and min of maxset is median
Code from https://github.com/epibook/epibook.github.io/blob/master/solutions/java/src/main/java/com/epi/OnlineMedian.java

ublic static void onlineMedian(InputStream sin) {

    // Min-heap stores the bigger part of the stream.

    PriorityQueue<Integer> H = new PriorityQueue<Integer>();

    // Max-heap stores the smaller part of the stream.

    PriorityQueue<Integer> L = new PriorityQueue<Integer>(11,

        new Comparator<Integer>() {

          @Override

          public int compare(Integer o1, Integer o2) {

            return o2.compareTo(o1);

          }

        });



    Scanner s = new Scanner(sin);

    while (s.hasNextInt()) {

      int x = s.nextInt();

      if (!L.isEmpty() && x > L.peek()) {

        H.add(x);

      } else {

        L.add(x);

      }

      if (H.size() > L.size() + 1) {

        L.add(H.remove());

      } else if (L.size() > H.size() + 1) {

        H.add(L.remove());

      }



      if (H.size() == L.size()) {

        System.out.println(0.5 * (H.peek() + L.peek()));

      } else {

        System.out.println((H.size() > L.size() ? H.peek() : L.peek()));

      }

    }

  }
Also read http://massivealgorithms.blogspot.com/2014/07/just-programming-interviewstreet-median.html
C++ code http://codercareer.blogspot.com/2012/01/no-30-median-in-stream.html

Read full article from Just Programming...: Interviewstreet Median Challenge Part 2 Solution C++