Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package testrun;
- import java.util.Comparator;
- import java.util.PriorityQueue;
- public class MedianInStream {
- double median = 0;
- // create a max heap
- PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(new Comparator<Integer>() {
- @Override
- public int compare(Integer o1, Integer o2) {
- return (int) (o1 - o2);
- }
- });
- // create a min heap
- PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(new Comparator<Integer>() {
- @Override
- public int compare(Integer o1, Integer o2) {
- return (int) (o2 - o1);
- }
- });
- public void insert(int number) {
- // Write your code here.
- if (minHeap.size() == 0 || minHeap.peek() > number) {
- minHeap.add(number);
- } else {
- maxHeap.add(number);
- }
- // rebalance heaps
- if (minHeap.size() - maxHeap.size() == 2) {
- maxHeap.add(minHeap.remove());
- } else if (maxHeap.size() - minHeap.size() == 2) {
- minHeap.add(maxHeap.remove());
- }
- // update median
- if (minHeap.size() == maxHeap.size()) {
- median = ((double) minHeap.peek() + (double) maxHeap.peek()) / 2;
- } else if (minHeap.size() > maxHeap.size()) {
- median = minHeap.peek();
- } else {
- median = maxHeap.peek();
- }
- }
- public double getMedian() {
- return median;
- }
- public static void main(String[] args) {
- MedianInStream ms = new MedianInStream();
- ms.insert(5);
- System.out.print("Median: " + ms.getMedian());
- ms.insert(10);
- System.out.print("Median: " + ms.getMedian());
- ms.insert(100);
- }
- }
Add Comment
Please, Sign In to add comment