获取数据流中的中位数

题目

有一个源源不断往外吐出整数的数据流，假设你有足够的空间来保存吐出的数。
请设计一个方法，这个方法可以随时取出之前吐出所有数的中位数

solution

1、建立一个大根堆和一个小根堆
2、首先往大根堆中添加一个数字
3、再次添加数字时，如果该数字<=大根堆堆顶的数字，就把该数字放入大根堆中，否则入小根堆
4、调整大小根堆的长度（如果|大根堆的长度-小根堆的长度|=2，将多的那个堆弹出一个数字放入另一个堆中）
循环3、4操作

代码：

import java.util.*;

public class MadianQuick {

    public static class MedianHolder {
        private PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(new MaxHeapComparator());
        private PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(new MinHeapComparator());

        //如果|大根堆的长度-小根堆的长度|=2，将多的那个堆弹出一个数字放入另一个堆中
        private void modifyTwoHeapsSize() {
            if (this.maxHeap.size() == this.minHeap.size() + 2) {
                this.minHeap.add(this.maxHeap.poll());
            }
            if (this.minHeap.size() == this.maxHeap.size() + 2) {
                this.maxHeap.add(this.minHeap.poll());
            }
        }

        //首先添加一个数字进大根堆
        //下次再添加数字时，如果该数字<=大根堆堆顶的数字，就把该数字放入大根堆中，否则入小根堆
        //然后调整大小根堆的长度（相差不能超过1）
        public void addNumber(int num) {
            if (maxHeap.isEmpty() || num <= maxHeap.peek()) {
                maxHeap.add(num);
            } else {
                minHeap.add(num);
            }
            modifyTwoHeapsSize();
        }

        public Integer getMedian() {
            int maxHeapSize = this.maxHeap.size();
            int minHeapSize = this.minHeap.size();
            if (maxHeapSize + minHeapSize == 0) {
                return null;
            }
            Integer maxHeapHead = this.maxHeap.peek();
            Integer minHeapHead = this.minHeap.peek();
            //如果观察值有偶数个，取最中间的两个数值的平均数作为中位数
            if (((maxHeapSize + minHeapSize) & 1) == 0) {
                return (maxHeapHead + minHeapHead) / 2;
            }
            //如果观察值有奇数个，取多的那个堆顶的数作为中位数
            return maxHeapSize > minHeapSize ? maxHeapHead : minHeapHead;
        }

    }

    public static class MaxHeapComparator implements Comparator<Integer> {
        @Override
        public int compare(Integer o1, Integer o2) {
            if (o2 > o1) {
                return 1;
            } else {
                return -1;
            }
        }
    }

    public static class MinHeapComparator implements Comparator<Integer> {
        @Override
        public int compare(Integer o1, Integer o2) {
            if (o2 < o1) {
                return 1;
            } else {
                return -1;
            }
        }
    }

   public static void main(String[] args) {
        int[] arr = {2, 8, 4, 6, 4, 6};
        Queue<Integer> queue = new LinkedList<>();
        MedianHolder medianHolder = new MedianHolder();
        for (int i = 0; i < arr.length; i++) {
            queue.offer(arr[i]);
            medianHolder.addNumber(arr[i]);
            Object[] objects = queue.toArray();
            Arrays.sort(objects);
            System.out.print("数字流为：");
            for (Object q:objects){
                System.out.print(q+" ");
            }
            System.out.print("中位数为：");
            System.out.println(medianHolder.getMedian());
        }
    }
}

/**
 * 数字流为：2 中位数为：2
 * 数字流为：2 8 中位数为：5
 * 数字流为：2 4 8 中位数为：4
 * 数字流为：2 4 6 8 中位数为：5
 * 数字流为：2 4 4 6 8 中位数为：4
 * 数字流为：2 4 4 6 6 8 中位数为：5
 */

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

public class MadianQuick {

    public static class MedianHolder {
        private PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(new MaxHeapComparator());
        private PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(new MinHeapComparator());

        //如果|大根堆的长度-小根堆的长度|=2，将多的那个堆弹出一个数字放入另一个堆中
        private void modifyTwoHeapsSize() {
            if (this.maxHeap.size() == this.minHeap.size() + 2) {
                this.minHeap.add(this.maxHeap.poll());
            }
            if (this.minHeap.size() == this.maxHeap.size() + 2) {
                this.maxHeap.add(this.minHeap.poll());
            }
        }

        //首先添加一个数字进大根堆
        //下次再添加数字时，如果该数字<=大根堆堆顶的数字，就把该数字放入大根堆中，否则入小根堆
        //然后调整大小根堆的长度（相差不能超过1）
        public void addNumber(int num) {
            if (maxHeap.isEmpty() || num <= maxHeap.peek()) {
                maxHeap.add(num);
            } else {
                minHeap.add(num);
            }
            modifyTwoHeapsSize();
        }

        public Integer getMedian() {
            int maxHeapSize = this.maxHeap.size();
            int minHeapSize = this.minHeap.size();
            if (maxHeapSize + minHeapSize == 0) {
                return null;
            }
            Integer maxHeapHead = this.maxHeap.peek();
            Integer minHeapHead = this.minHeap.peek();
            //如果观察值有偶数个，取最中间的两个数值的平均数作为中位数
            if (((maxHeapSize + minHeapSize) & 1) == 0) { 
                return (maxHeapHead + minHeapHead) / 2; 
            }
            //如果观察值有奇数个，取多的那个堆顶的数作为中位数
            return maxHeapSize > minHeapSize ? maxHeapHead : minHeapHead;
        }

    }

    public static class MaxHeapComparator implements Comparator<Integer> {
        @Override
        public int compare(Integer o1, Integer o2) {
            if (o2 > o1) {
                return 1;
            } else {
                return -1;
            }
        }
    }

    public static class MinHeapComparator implements Comparator<Integer> {
        @Override
        public int compare(Integer o1, Integer o2) {
            if (o2 < o1) {
                return 1;
            } else {
                return -1;
            }
        }
    }

    //#####################以下代码为使用对数器测试上面算法是否正确##################

    // for test
    public static int[] getRandomArray(int maxLen, int maxValue) {
        int[] res = new int[(int) (Math.random() * maxLen) + 1];
        for (int i = 0; i != res.length; i++) {
            res[i] = (int) (Math.random() * maxValue);
        }
        return res;
    }

    // for test, this method is ineffective but absolutely right
    public static int getMedianOfArray(int[] arr) {
        int[] newArr = Arrays.copyOf(arr, arr.length);
        Arrays.sort(newArr);
        int mid = (newArr.length - 1) / 2;
        if ((newArr.length & 1) == 0) {
            return (newArr[mid] + newArr[mid + 1]) / 2;
        } else {
            return newArr[mid];
        }
    }

    public static void printArray(int[] arr) {
        for (int i = 0; i != arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        boolean err = false;
        int testTimes = 200000;
        for (int i = 0; i != testTimes; i++) {
            int len = 30;
            int maxValue = 1000;
            int[] arr = getRandomArray(len, maxValue);
            MedianHolder medianHold = new MedianHolder();
            for (int j = 0; j != arr.length; j++) {
                medianHold.addNumber(arr[j]);
            }
            if (medianHold.getMedian() != getMedianOfArray(arr)) {
                err = true;
                printArray(arr);
                break;
            }
        }
        System.out.println(err ? "Oops..what a fuck!" : "today is a beautiful day^_^");
    }

}