mjain

Median In Incoming stream of Numbers

Jul 24th, 2019
33
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.08 KB | None | 0 0
  1. package testrun;
  2.  
  3. import java.util.Comparator;
  4. import java.util.PriorityQueue;
  5.  
  6. public class MedianInStream {
  7.  
  8.     double                 median  = 0;
  9.     // create a max heap
  10.     PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(new Comparator<Integer>() {
  11.                                        @Override
  12.                                        public int compare(Integer o1, Integer o2) {
  13.                                            return (int) (o1 - o2);
  14.                                        }
  15.                                    });
  16.     // create a min heap
  17.     PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(new Comparator<Integer>() {
  18.                                        @Override
  19.                                        public int compare(Integer o1, Integer o2) {
  20.                                            return (int) (o2 - o1);
  21.                                        }
  22.                                    });
  23.  
  24.     public void insert(int number) {
  25.         // Write your code here.
  26.         if (minHeap.size() == 0 || minHeap.peek() > number) {
  27.             minHeap.add(number);
  28.         } else {
  29.             maxHeap.add(number);
  30.         }
  31.         // rebalance heaps
  32.         if (minHeap.size() - maxHeap.size() == 2) {
  33.             maxHeap.add(minHeap.remove());
  34.         } else if (maxHeap.size() - minHeap.size() == 2) {
  35.             minHeap.add(maxHeap.remove());
  36.         }
  37.         // update median
  38.         if (minHeap.size() == maxHeap.size()) {
  39.             median = ((double) minHeap.peek() + (double) maxHeap.peek()) / 2;
  40.         } else if (minHeap.size() > maxHeap.size()) {
  41.             median = minHeap.peek();
  42.         } else {
  43.             median = maxHeap.peek();
  44.         }
  45.  
  46.     }
  47.  
  48.     public double getMedian() {
  49.         return median;
  50.     }
  51.  
  52.     public static void main(String[] args) {
  53.         MedianInStream ms = new MedianInStream();
  54.         ms.insert(5);
  55.         System.out.print("Median: " + ms.getMedian());
  56.         ms.insert(10);
  57.         System.out.print("Median: " + ms.getMedian());
  58.         ms.insert(100);
  59.        
  60.  
  61.     }
  62. }
Add Comment
Please, Sign In to add comment