SolutionHeap.java

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class SolutionHeap {
    
    private static class BinaryMinHeap {
        /** The number of children each node has **/
        protected static final int d = 2;
        protected int heapSize;
        protected int[] heap;

        /** Constructor **/    
        public BinaryMinHeap(int capacity)
        {
            heapSize = 0;
            heap = new int[capacity + 1];
            Arrays.fill(heap, -1);
        }
        
        public int size() {
            return heapSize;
        }
        
        public int get(int index) {
            return heap[index];
        }
        
        public void set(int index, int value) {
            heap[index] = value;
        }

        /** Function to check if heap is empty **/
        public boolean isEmpty( )
        {
            return heapSize == 0;
        }

        /** Check if heap is full **/
        public boolean isFull( )
        {
            return heapSize == heap.length;
        }

        /** Function to  get index parent of i **/
        protected int parent(int i) 
        {
            return (i - 1)/d;
        }

        /** Function to get index of k th child of i **/
        protected int kthChild(int i, int k) 
        {
            return d * i + k;
        }

        /** Function to insert element */
        public void insert(int x)
        {
            if (isFull( ) )
                throw new NoSuchElementException("Overflow Exception");
            /** Percolate up **/
            heap[heapSize++] = x;
            heapifyUp(heapSize - 1);
        }

        /** Function heapifyUp  **/
        public void heapifyUp(int childInd)
        {
            int tmp = heap[childInd];    
            while (childInd > 0 && tmp > heap[parent(childInd)])
            {
                heap[childInd] = heap[ parent(childInd) ];
                childInd = parent(childInd);
            }                   
            heap[childInd] = tmp;
        }

        /** Function heapifyDown **/
        public void heapifyDown(int ind)
        {
            int child;
            int tmp = heap[ ind ];
            while (kthChild(ind, 1) < heapSize)
            {
                child = maxChild(ind);
                if (heap[child] > tmp)
                    heap[ind] = heap[child];
                else
                    break;
                ind = child;
            }
            heap[ind] = tmp;
        }

        /** Function to get smallest child **/
        protected int minChild(int ind) 
        {
            int bestChild = kthChild(ind, 1);
            int k = 2;
            int pos = kthChild(ind, k);
            while ((k <= d) && (pos < heapSize)) 
            {
                if (heap[pos] < heap[bestChild]) 
                    bestChild = pos;
                pos = kthChild(ind, k++);
            }    
            return bestChild;
        }

        /** Function to get smallest child **/
        protected int maxChild(int ind) 
        {
            int bestChild = kthChild(ind, 1);
            int k = 2;
            int pos = kthChild(ind, k);
            while ((k <= d) && (pos < heapSize)) 
            {
                if (heap[pos] > heap[bestChild]) 
                    bestChild = pos;
                pos = kthChild(ind, k++);
            }    
            return bestChild;
        }

        /** Function to print heap **/
        public void printHeap()
        {
            System.out.print("\nHeap = ");
            for (int i = 0; i < heapSize; i++)
                System.out.print(heap[i] +" ");
            System.out.println();
        }     
    }
    
    private static final class BinaryMaxHeap extends BinaryMinHeap {
        public BinaryMaxHeap(int capacity)
        {
            super(capacity);
        }
        
        /** Function heapifyUp  **/
        public void heapifyUp(int childInd)
        {
            int tmp = heap[childInd];    
            while (childInd > 0 && tmp < heap[parent(childInd)])
            {
                heap[childInd] = heap[ parent(childInd) ];
                childInd = parent(childInd);
            }                   
            heap[childInd] = tmp;
        }

        /** Function heapifyDown **/
        public void heapifyDown(int ind)
        {
            int child;
            int tmp = heap[ ind ];
            while (kthChild(ind, 1) < heapSize)
            {
                child = minChild(ind);
                if (heap[child] < tmp)
                    heap[ind] = heap[child];
                else
                    break;
                ind = child;
            }
            heap[ind] = tmp;
        }
    }
    
    private static final class MedianHeap {
        public int root;
        public BinaryMinHeap minHeap;
        public BinaryMaxHeap maxHeap;
        boolean leftTurn = true;
        
        public MedianHeap(int size) {
            minHeap = new BinaryMinHeap(size/2);
            maxHeap = new BinaryMaxHeap(size/2);
        }
        
        public double median() {
            if (leftTurn)
                return (double)root;
            else
                return (root + minHeap.get(0))/2.0;
        }
        
        public void insert(int i) {
                if (leftTurn) {
                    minHeap.insert(i);
                    if (root < minHeap.get(0)){
                        int temp = root;
                        root = minHeap.get(0);
                        minHeap.set(0, temp);
                    }
                    if (maxHeap.size() > 0 && root > maxHeap.get(0)){
                        int temp = root;
                        root = maxHeap.get(0);
                        maxHeap.set(0, temp);
                        maxHeap.heapifyDown(0);
                    }
                } else {
                    maxHeap.insert(i);
                    if (root > maxHeap.get(0)){
                        int temp = root;
                        root = maxHeap.get(0);
                        maxHeap.set(0, temp);
                    }
                    if (root < minHeap.get(0)){
                        int temp = root;
                        root = minHeap.get(0);
                        minHeap.set(0, temp);
                        minHeap.heapifyDown(0);
                    }
                }
                leftTurn = !leftTurn;
        }
        
        public void print() {
            System.out.println("ROOT:: " + root);
            minHeap.printHeap();
            maxHeap.printHeap();
        }
    }
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        MedianHeap heap = new MedianHeap(n);
        heap.root = in.nextInt();
        System.out.println(heap.median());
        for(int a_i=1; a_i < n; a_i++){
            heap.insert(in.nextInt());
            System.out.println(heap.median());
        }
    }
}