Created
July 14, 2017 09:19
-
-
Save anil477/63d2f76cf659ef33dc65604cfd05e4ee to your computer and use it in GitHub Desktop.
Median in a stream of integers (running integers)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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