Calculate median using priority queues

Question

I'm required to calculate the median. I've been told that the best way to do this is in this particular application is with a priority queue. I have no clue on how to proceed. I'd really appreciate any help.

Answer 1

This should do it. Maintain two priority queues of the numbers greater and less than the median value. Shift values between the two queues such that they stay balanced, or close to balanced, and define the median based on the top values of the priority queues.

#include <queue>
#include <vector>
#include <functional>
#include <limits>
#include <iostream>

template<class T>
class RunningMedian {
 private:
  //Values greater than the median sorted so that smallest is on top
  std::priority_queue<T, std::vector<T>, std::greater<T> > upper;
  //Values smaller than the median sorted so that greatest is on top
  std::priority_queue<T, std::vector<T>, std::less<T> > lower;

 public:
  RunningMedian(){
    //Seed the queues
    upper.push(std::numeric_limits<T>::max());
    lower.push (std::numeric_limits<T>::min());
  }
  void push(T val){
    //Add number to the property queue

    //If number is greater than the least upper number, it is an upper number
    if(val>=upper.top())
      upper.push(val);
    else //Otherwise it is a lower number
      lower.push(val);

    //Rebalance
    //If the queues sizes differ by 2, they need to be rebalanced so that they
    //differ by 1.
    if(upper.size()-lower.size()==2){ //Upper queue is larger
      lower.push(upper.top());        //Move value from upper to lower
      upper.pop();                    //Remove same value from upper
    } else if(lower.size()-upper.size()==2){ //Lower queue is larger
      upper.push(lower.top());               //Move value from lower to upper
      lower.pop();                           //Remove same value
    }
  }

  T getMedian() const {
    if(upper.size()==lower.size())               //Upper and lower are same size
      return(upper.top()+lower.top())/((T)2.0);  //so median is average of least upper and greatest lower
    else if(upper.size()>lower.size())           //Upper size greater
      return upper.top();
    else                                         //Lower size greater
      return lower.top();
  }
};

int main(){
  RunningMedian<int> rm;
  rm.push(10);
  rm.push(3);
  rm.push(1);
  rm.push(20);
  rm.push(5);
  rm.push(8);
  rm.push(-1);
  std::cout<<rm.getMedian()<<std::endl; //Gives 5
}

Answer 2

@Richard's code produces undefined behavior. You can refer to this. To sum up, when you call PQ.top on the empty priority queue, you will make undefined behavior.

I will use negating method to make the smallest number of the original upper half in a max heap the largest.

class FindMedian{
    /* the largest number in lower half */
    std::priority_queue<int> small;
    /* the largest negative number in upper half */
    std::priority_queue<int> large;
    public:
        void add(int num) {
            small.push(num);
            large.push(-small.top());
            /*In order to rearrange small.top() later
            * e.g., assume that small = {2} and large = {-4}
            * Now, we want to push 5 into the small, so small = {5, 2} and 
            * large = {-4, -5}
            * However, the small.top() is larger than (-large.top()).
            * Thus, we need to rearrange them and first pop out in small container
            */
            small.pop();
            //we ensure that the size of small is equal to or one more than large
            if (small.size() < large.size()) {
                small.push(-large.top());
                large.pop();
            }

        }
        double findMedian() {
            return small.size() > large.size() ?
               //if total size is odd or if total size is even 
                small.top() : ((small.top() - large.top()) >> 1);
        }
    };

Basically, The principle behind the code is the same as Richard's.