title: How to implement a Median-heap
body: <p>Like a Max-heap and Min-heap, I want to implement a Median-heap to keep track of the median of a given set of integers. The API should have the following three functions:</p>
  
  <pre><code>insert(int)  // should take O(logN)
  int median() // will be the topmost element of the heap. O(1)
  int delmedian() // should take O(logN)
  </code></pre>
  
  <p>I want to use an array (a) implementation to implement the heap where the children of array index k are stored in array indices 2*k and 2*k + 1. For convenience, the array starts populating elements from index 1. 
  This is what I have so far:
  The Median-heap will have two integers to keep track of number of integers inserted so far that are > current median (gcm) and &lt; current median (lcm). </p>
  
  <pre><code>if abs(gcm-lcm) &gt;= 2 and gcm &gt; lcm we need to swap a[1] with one of its children. 
  The child chosen should be greater than a[1]. If both are greater, 
  choose the smaller of two.
  </code></pre>
  
  <p>Similarly for the other case. I can't come up with an algorithm for how to sink and swim elements. I think it should take into consideration how close the number is to the median, so something like:</p>
  
  <pre><code>private void swim(int k) {
      while (k &gt; 1 &amp;&amp; absless(k, k/2)) {   
          exch(k, k/2);
          k = k/2;
      }
  }
  </code></pre>
  
  <p>I can't come up with the entire solution though. </p>