Skip to content

Instantly share code, notes, and snippets.

@rajatdiptabiswas
Created July 27, 2018 03:37
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 rajatdiptabiswas/49a8dfa70e3a8432e752cacd71becb86 to your computer and use it in GitHub Desktop.
Save rajatdiptabiswas/49a8dfa70e3a8432e752cacd71becb86 to your computer and use it in GitHub Desktop.
Find the median in a stream of integers (running integers)
import java.io.*;
import java.math.*;
import java.util.*;
import java.lang.*;
public class StreamMedian {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
PriorityQueue<Double> rightMinHeap = new PriorityQueue<>();
PriorityQueue<Double> leftMaxHeap = new PriorityQueue<>(10, Collections.reverseOrder());
double currentMedian = scan.nextDouble();
System.out.println("Current median : " + currentMedian);
leftMaxHeap.add(currentMedian);
while (true) {
double input = scan.nextDouble();
if (input == -1) {
break;
}
if (input < currentMedian)
leftMaxHeap.add(input);
else
rightMinHeap.add(input);
while (Math.abs(leftMaxHeap.size() - rightMinHeap.size()) > 1) {
if (leftMaxHeap.size() > rightMinHeap.size()) {
rightMinHeap.add(leftMaxHeap.poll());
} else {
leftMaxHeap.add(rightMinHeap.poll());
}
}
if (leftMaxHeap.size() == rightMinHeap.size()) {
currentMedian = (leftMaxHeap.peek() + rightMinHeap.peek())/2.0;
} else {
if (leftMaxHeap.size() > rightMinHeap.size()) {
currentMedian = leftMaxHeap.peek();
} else {
currentMedian = rightMinHeap.peek();
}
}
System.out.println("Current median : " + currentMedian);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment