CTCI Challange, DAY 8

Day 8:- 

Problem statement:- Heaps: Find the Running Median

I have studied a lot on heaps,but this is the first implementation by me.

Thought the problem is very easy,but solving with time constraint using heaps priority queues was very time consuming.
I implemented it using heapsort.

On paper:-

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author vikram.shanbogar@gmail.com
 * on 8/2/2017.
 */
public class Heaps {
    static int index;
    static int[] a;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        a = new int[n];
        for (int a_i = 0; a_i < n; a_i++) {
            //a[a_i] = in.nextInt();
            index = a_i;
            insert(in.nextInt());
        }
    }

    private static void insert(int data) {
        a[index] = data;
        if (index == 0) {
            System.out.printf("%.1f\n", (float) a[index]);
            return;
        }
        sort(a);
        calcMedian(a);
    }

    private static void calcMedian(int[] temp) {
        float median;
        int x = index + 1;
        if (x % 2 == 0)
            median = (float) (temp[(x / 2)] + temp[(x / 2) - 1]) / 2;
        else
            median = (float) temp[(x / 2)];
        System.out.printf("%.1f\n", median);
    }

    public static int[] sort(int[] pq) {
        int n = index + 1;
        for (int k = n / 2; k >= 1; k--)
            sink(pq, k, n);
        while (n > 1) {
            exch(pq, 1, n--);
            sink(pq, 1, n);
        }
        return pq;
    }

    private static void sink(int[] pq, int k, int n) {
        while (2 * k <= n) {
            int j = 2 * k;
            if (j < n && less(pq, j, j + 1)) j++;
            if (!less(pq, k, j)) break;
            exch(pq, k, j);
            k = j;
        }
    }

    private static boolean less(int[] pq, int i, int j) {
        return (pq[i - 1] < (pq[j - 1]));
    }

    private static void exch(int[] pq, int i, int j) {
        int swap = pq[i - 1];
        pq[i - 1] = pq[j - 1];
        pq[j - 1] = swap;
    }
}

Note:-
Updated on 18th Aug.
tried with new approach as few of the test cases were not running with the above solution.

import edu.princeton.cs.algs4.MaxPQ;
import edu.princeton.cs.algs4.MinPQ;

import java.util.*;

/** * @author vikram.shanbogar@gmail.com * on 8/2/2017. */

public class Heaps2 {
    static int index;
    static int[] a;

    static Queue<Integer> leftQueue = new PriorityQueue<>
            (Collections.reverseOrder());
    static Queue<Integer> rightQueue = new PriorityQueue<>();

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();

        for (int a_i = 0; a_i < n; a_i++) {
            index = a_i;
            //insert(in.nextInt());           

            int val = in.nextInt();
            insert(val);
            System.out.println(calcMedian());
        }
    }

    private static void insert(int val) {
        Queue q;
        if (leftQueue.size() <= rightQueue.size()) {
            q = leftQueue;
        } else            q = rightQueue;
        q.add(val);
        if (!leftQueue.isEmpty() && !rightQueue.isEmpty() 
                && leftQueue.peek() > rightQueue.peek()) {
            int left = leftQueue.poll();
            int right = rightQueue.poll();
            leftQueue.add(right);
            rightQueue.add(left);
        }
    }

    private static float calcMedian() {
        if (leftQueue.size() == rightQueue.size()) {
            return (float) (leftQueue.peek() + rightQueue.peek()) / 2;
        } else            

         return leftQueue.peek();
    }
}