Skip to content

Instantly share code, notes, and snippets.

@anil477
Created July 14, 2017 09:19
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save anil477/63d2f76cf659ef33dc65604cfd05e4ee to your computer and use it in GitHub Desktop.
Save anil477/63d2f76cf659ef33dc65604cfd05e4ee to your computer and use it in GitHub Desktop.
Median in a stream of integers (running integers)
// https://www.youtube.com/watch?v=VmogG01IjYc
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
class MedianOfIntegerStream {
public PriorityQueue<Integer> lower;
public PriorityQueue<Integer> higher;
public MedianOfIntegerStream()
{
lower = new PriorityQueue<Integer>(10, new MaxHeapComparator());
higher = new PriorityQueue<Integer>();
}
public double getMedian()
{
if (lower.size() == higher.size()) {
return ((double)lower.peek() + (double)higher.peek())/2;
} else {
return lower.peek();
}
}
public void addNumberToStream(Integer n)
{
if(lower.size() == 0 || n < lower.peek() ){
// System.out.println(" Adding to Lower " + n);
lower.add(n);
} else{
// System.out.println(" Adding to Higher " + n);
higher.add(n);
}
balance();
}
public void balance()
{
PriorityQueue<Integer> smaller = lower.size() < higher.size() ? lower : higher;
PriorityQueue<Integer> bigger = lower.size() > higher.size() ? lower : higher;
if((bigger.size() - smaller.size()) >= 2)
{
// System.out.println(" Moving Element: " + bigger.peek());
smaller.add(bigger.poll());
}
}
private class MaxHeapComparator implements Comparator<Integer> {
@Override
public int compare(Integer o1, Integer o2) {
return -1 * o1.compareTo(o2);
}
}
public void print()
{
System.out.println(lower);
System.out.println(higher);
}
public static void main(String[] args) {
MedianOfIntegerStream streamMedian = new MedianOfIntegerStream();
streamMedian.addNumberToStream(1);
System.out.println(streamMedian.getMedian()); // should be 1
streamMedian.addNumberToStream(5);
streamMedian.addNumberToStream(10);
streamMedian.addNumberToStream(12);
streamMedian.addNumberToStream(2);
System.out.println(streamMedian.getMedian()); // should be 5
streamMedian.addNumberToStream(3);
streamMedian.addNumberToStream(8);
streamMedian.addNumberToStream(9);
System.out.println(streamMedian.getMedian()); // should be 6.5
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment