@@ -0,0 +1,1901 @@
+import java.io.*;%0Aimport java.util.*;%0Aimport java.text.*;%0Aimport java.math.*;%0Aimport java.util.regex.*;%0A%0Aclass MedianHeap %7B%0A%0A    public PriorityQueue%3CInteger%3E minHeap;%0A    public PriorityQueue%3CInteger%3E maxHeap;%0A%0A    public MedianHeap(int capacity) %7B%0A        this.minHeap = new PriorityQueue(capacity);%0A        this.maxHeap = new PriorityQueue(capacity, Collections.reverseOrder());%0A    %7D%0A%0A    public void add(int num) %7B%0A        if (isEmpty()) %7B%0A            this.minHeap.add(num);%0A        %7D else if (num %3E= median()) %7B%0A            this.minHeap.add(num);%0A        %7D else %7B%0A            this.maxHeap.add(num);%0A        %7D%0A        rebalanceHeaps();%0A    %7D%0A%0A    public double median() %7B%0A        if (minHeap.size() %3E maxHeap.size()) %7B%0A            return minHeap.peek();%0A        %7D else if (minHeap.size() %3C maxHeap.size()) %7B%0A            return maxHeap.peek();%0A        %7D else %7B%0A            return ((minHeap.peek() + maxHeap.peek()) / 2.0);%0A        %7D%0A    %7D%0A%0A    private boolean isEmpty() %7B%0A        return (minHeap.size() == 0 && maxHeap.size() == 0);%0A    %7D%0A%0A    private void rebalanceHeaps() %7B%0A        if (minHeap.size() - maxHeap.size() %3E 1) %7B%0A            maxHeap.add(minHeap.poll());%0A        %7D%0A        if (maxHeap.size() - minHeap.size() %3E 1) %7B%0A            minHeap.add(maxHeap.poll());%0A        %7D%0A    %7D%0A%0A%7D%0A%0Apublic class Solution %7B%0A%0A    public static void main(String%5B%5D args) %7B%0A        Scanner in = new Scanner(System.in);%0A        int capacity = in.nextInt();%0A        int%5B%5D list = new int%5Bcapacity%5D;%0A        MedianHeap medianHeap = new MedianHeap(capacity);%0A%0A        for(int i = 0; i %3C capacity; i++)%7B%0A            list%5Bi%5D = in.nextInt();%0A            medianHeap.add(list%5Bi%5D);%0A            //System.out.println(%22minHeap: %22 + medianHeap.minHeap.toString());%0A            //System.out.println(%22maxHeap: %22 + medianHeap.maxHeap.toString());%0A            System.out.printf(%22%25.1f%5Cn%22, medianHeap.median());%0A        %7D%0A    %7D%0A%7D%0A%0A%0A

Solve Median w/ two heaps