随时获取数据流的中位数

import java.util.Comparator;
import java.util.PriorityQueue;

public class GetMedian {

    public static class MinHeapComparator implements Comparator<Integer> {

        @Override
        public int compare(Integer a, Integer b) {
            return a > b ? 1 : -1;
        }
    }

    public static class MaxHeapComparator implements Comparator<Integer> {

        @Override
        public int compare(Integer a, Integer b) {
            return b > a ? 1 : -1;
        }
    }

    public static void main(String[] args) {
        int[] arr = { 8, 3, 4, 6, 9, 7, 1 }; // 1 3 4 6 7 8 9
        double median = getMedian(arr);
        System.out.println(median);
    }

    private static double getMedian(int[] arr) {
        PriorityQueue<Integer> big = new PriorityQueue<Integer>(new MaxHeapComparator());
        PriorityQueue<Integer> small = new PriorityQueue<Integer>(new MinHeapComparator());
        for (int i = 0; i < arr.length; i++) {
            int cur = arr[i];
            if (big.isEmpty() || cur < big.peek())
                big.add(cur);
            else
                small.add(cur);
            if (big.size() - small.size() >= 2)
                small.add(big.poll());
            else if (small.size() - big.size() >= 2)
                big.add(small.poll());
        }
        if (arr.length % 2 == 0)
            return ((double) (big.peek() + small.peek()) / 2);
        else
            return big.size() > small.size() ? big.peek() : small.peek();
    }
}