1class MedianOfIntegerStream {
2
3 private Queue<Integer> minHeap, maxHeap;
4
5 MedianOfIntegerStream() {
6 minHeap = new PriorityQueue<>();
7 maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
8 }
9
10 void add(int num) {
11 if (!minHeap.isEmpty() && num < minHeap.peek()) {
12 maxHeap.offer(num);
13 if (maxHeap.size() > minHeap.size() + 1) {
14 minHeap.offer(maxHeap.poll());
15 }
16 } else {
17 minHeap.offer(num);
18 if (minHeap.size() > maxHeap.size() + 1) {
19 maxHeap.offer(minHeap.poll());
20 }
21 }
22 }
23
24 double getMedian() {
25 int median;
26 if (minHeap.size() < maxHeap.size()) {
27 median = maxHeap.peek();
28 } else if (minHeap.size() > maxHeap.size()) {
29 median = minHeap.peek();
30 } else {
31 median = (minHeap.peek() + maxHeap.peek()) / 2;
32 }
33 return median;
34 }
35}