Find Median from Data Stream

Find the median of the running stream. Median is the middle element when we sort them.

Example:

Input: arr[]={2,3,4}
Output: 2 2.5 3
 

Approach:

Java

import java.util.PriorityQueue;

public class MedianFinderStream {

    public static void main(String[] args) {
        MedianFinder m = new MedianFinder();
        m.addNum(2);
        System.out.println(m.findMedian());
        m.addNum(3);
        System.out.println(m.findMedian());
        m.addNum(4);
        System.out.println(m.findMedian());
    }
}

class MedianFinder {
    // maximum priority queue
    PriorityQueue<Integer> max = 
            new PriorityQueue<>((a, b) -> b - a);
    // minimum priority queue
    PriorityQueue<Integer> min = new PriorityQueue<>();
    // variable to hold the median
    double median = 0;

    /** initialize your data structure here. */
    public MedianFinder() {

    }

    public void addNum(int num) {
        // if both are of equal size
        if (max.size() == min.size()) {
            // if current element is
            // greater than median then
            // push into minimum priority
            // queue and set median as top
            // of min priority queue
            if (num > median) {
                min.add(num);
                median = min.peek();
            }

            // else push into the max queue
            // and set median as top of max queue
            else {
                max.add(num);
                median = max.peek();
            }
        }

        // if min size is more
        else if (min.size() > max.size()) {
            // if element is more than median
            // then push the top of min into max
            // and current element into the min
            if (num > median) {
                max.add(min.poll());
                min.add(num);
            }
            // else push into the max
            else
                max.add(num);

            // set median as average of
            // min top and max top elements
            median = (double) (min.peek() + max.peek()) / 2;

        }
        // if max size if greater
        else {
            // if current is more than then
            // median then push into the min
            // queue
            if (num > median) {
                min.add(num);
            }

            // else push the top of max into
            // the min and current into the max
            else {
                min.add(max.poll());
                max.add(num);
            }
            // set the median as average of
            // top of min and max
            median = (double) (min.peek() + max.peek()) / 2;
        }
    }

    public double findMedian() {
        return median;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

//maximum priority queue
priority_queue<double> max1;

//minimum priority queue
priority_queue<double,vector<double>,greater<double>> min1;

//variable to hold the median
double median=0;

//add numner into the priority
//queues
void addNum(int num) 
{

    //if both are of equal size

    if(max1.size()==min1.size())
        {

            //if current element is 
            //greter than median then
            //push into minimum priority
            //queue and set meadin as top
            //of min priority queue
            if(num>median)
            {
                min1.push(num);
                median=min1.top();
            }

           //else push into the max  queue
           //and set median as top of max queue
            else
            {
                max1.push(num);
                median=max1.top();
            }
       }

       //if min size is more
        else if(min1.size()>max1.size())
        {

            //if element is more than median
            //then push the top of min into max
            //and current element into the min
            if(num>median)
            {
                max1.push(min1.top());
                min1.pop();
                min1.push(num);
            }
          //else push into the max
            else
                 max1.push(num);

            //set median as average of
            //min top and max top elements
            median=(min1.top()+max1.top())/2;
            
        }
       //if max size if greater
        else
        {
            //if current is more than then
            //median then push into the min
            //queue
            if(num>median)
            {
                min1.push(num);
            }

            //else push the top of max into
            //the min and current into the max
            else
            {
                min1.push(max1.top());
                max1.pop();
                max1.push(num);
            }
            //set the median as average of
            //top of min and max
            median=(min1.top()+max1.top())/2;
        }
}

//function to find the meadin of running
//stream     
double findMedian() {
        return median;
}
int main()
{
    int arr[]={2,3,4};
    int n=sizeof(arr)/sizeof(arr[0]);
    for(int i=0;i<n;i++)
      {
          addNum(arr[i]);
          cout<<findMedian()<<" ";
      }
    return 0;
}