Median By Heap

Median By Heap

  May 25, 2017    

---

Problem ; Running Median
Problem : Find median in a stream

Solution :

Here we are using two heaps (Max ,min ) such that we will create two part of the numbers and numbers less than median stored in one heap and rest into another.

Methods :

First add numbers to heap 

Then Re balance heap structure

Store median for each value in array and return to main function.

Method 1:check if max heap is empty or number is smaller than max heap top then push into max heap else into min heap. (Here naming is little bit change from min to mix and vice versa).

Method 2: Re balance:check for smaller and bigger heap and check if length is 2 then switch element from bigger to smaller .Length won't be greater than 2 here.

method 3 : getmedian
here we will check if length of both the heaps and equal then return sum of both top/2elsereturn top of maximum number.

Code: 

import java.io.*;

import java.util.*;

import java.text.*;

import java.math.*;

import java.util.regex.*;

public class median {

    public static void addnumber(int n,PriorityQueue<Integer> minheap,PriorityQueue<Integer> maxheap)

        {

        if(minheap.size()==0 || n<minheap.peek())

            minheap.offer(n);

        else

           maxheap.offer(n);

    }

    public static void rebalance(PriorityQueue<Integer> minheap,PriorityQueue<Integer> maxheap)

        {

        PriorityQueue<Integer> biggerheap=minheap.size()>maxheap.size()?minheap:maxheap;

        PriorityQueue<Integer> smallerheap=minheap.size()>maxheap.size()?maxheap:minheap;

        if(biggerheap.size()-smallerheap.size()>=2)

            {

            smallerheap.add(biggerheap.poll());

        }

    }

    public static double getMedian(PriorityQueue<Integer> minheap,PriorityQueue<Integer> maxheap)

        {

         PriorityQueue<Integer> biggerheap=minheap.size()>maxheap.size()?minheap:maxheap;

        PriorityQueue<Integer> smallerheap=minheap.size()>maxheap.size()?maxheap:minheap;

       if(biggerheap.size()==smallerheap.size())

           return((double)(biggerheap.peek()+smallerheap.peek()))/2;

                  else

                  return (biggerheap.peek());

    }

    public static double[] getmedian(int[] arr)

        {

        PriorityQueue<Integer> minheap=new PriorityQueue<Integer>(Collections.reverseOrder());

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

        double median[]=new double[arr.length];

        for(int i=0;i<arr.length;++i)

            {

            addnumber(arr[i],minheap,maxheap);

            rebalance(minheap,maxheap);

            median[i]=getMedian(minheap,maxheap);

        }

        return median;

    }

    public static void main(String args[] ) throws Exception {

        Scanner ab=new Scanner(System.in);

        int n=ab.nextInt();

        int arr[]=new int[n];

        int i=0;

        while(i<n){

            arr[i++]=ab.nextInt();

        }

        double res[]=getmedian(arr);

        for(double c:res)

            System.out.println(c);

        

    }

}