How to find Median in a stream of integers (running integers) in C ++

In this topic, we are going to learn how to find median in a stream of integers ie. running integers.  First of all, we are going to discuss the Median.

Median can be simply stated as the middle of the sorted list numbers, which means if we take a list of numbers that are placed in sorted order then we generally consider the element which is placed in the middle as a median if the list is of odd numbers.

But if we came across the list with even numbers of an element then we will take an average of the two middle elements and the result will be called a median of the list.

Example:
        Input:10 20 30
        Output:10
               15
               20

Explanation:
While working on the list we encountered the first element as 10 and as we came across only one element the median is 10.Then we encountered the 2nd element as 20 then we take the average as 15,
then 3rd element came as 30 then we will consider the 2nd element as a median, which means 20.

C++ Code to find median in a stream of integers

// C++ program to find med in
// stream of running integers
#include<bits/stdc++.h>
using namespace std;

// function to calculate median of stream
void showm(double d[], int n)
{
  priority_queue<double> s;
  priority_queue<double,vector<double>,greater<double> > g;

  double md = d[0];
  s.push(d[0]);

  cout << md << endl;

  for (int i=1; i < n; i++)
  {
    double x = d[i];

    //  more elements in left side heap
    if (s.size() > g.size())
    {
      if (x < md)
      {
        g.push(s.top());
        s.pop();
        s.push(x);
      }
      else
        g.push(x);

      md = (s.top() + g.top())/2.0;
    }

    //  balanced heaps
    else if (s.size()==g.size())
    {
      if (x < md)
      {
        s.push(x);
        md = (double)s.top();
      }
      else
      {
        g.push(x);
        md = (double)g.top();
      }
    }

    // right side heap has more elements
    else
    {
      if (x > md)
      {
        s.push(g.top());
        g.pop();
        g.push(x);
      }
      else
        s.push(x);

      md = (s.top() + g.top())/2.0;
    }

    cout << md << endl;
  }
}

int main()
{
  // stream of integers
  double d[] = {10 20 30};
  int p = sizeof(d)/sizeof(d[0]);
  showm(d, p);
  return 0;
}
Output:10
       15
       20

You can also be referred to:

Leave a Reply

Your email address will not be published.