[剑指offer][Java]数据流中的中位数

题目

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

程序核心思想

核心思想大家应该都是一样的，用堆结构来做。
构造一个大根堆，一个小根堆，数据流中出来一个数，那么如果这个数比大根堆的堆顶还要大，那么这个数进入小根堆的底部，然后heapify调整（跟它的父节点比较，如果比父节点小，那么交换...），如果比大根堆的堆顶小，那么进入大根堆的底部，然后heapify调整（跟它的父节点比较，如果比父节点大，那么交换...）。同时还有记录进入大根堆和小根堆的总数，如果大根堆和小根堆的差大于1的话，那么如果大根堆的总数比小根堆多，那么把大根堆的堆顶放入小根堆，否则把小根堆的堆顶放入大根堆，然后大根堆和小根堆都要heapify，弹出东西的那个堆的heapify是从index=0的位置开始（因为做了一个swap（0，堆底）的操作），放入东西的那个堆的heapify还是跟之前一样，是从堆底到堆顶的。
剩下的就是输出一个数还是两个数的平均数的部分了，比较简单，不说了。

然后我发现，网路上面的解法比我的要简单很多，因为他们使用了一个叫做优先队列的结构。
PriorityQueue通过二叉小顶堆实现，可以用一棵完全二叉树表示。优先队列的作用是能保证每次取出的元素都是队列中权值最小的，这里牵涉到了大小关系，元素大小的评判可以通过元素本身的自然顺序（natural ordering），也可以通过构造时传入的比较器（Comparator）。

Tips

插入元素：add()、offer()
删除元素：poll()
获取队头元素：peek()
获取队列大小：size()
清空队列：clear()
是否包含某个元素：contains()
清除一个指定元素：remove()

优先队列默认按从小到大的顺序排列，如果需要一个大顶堆的话，需要重写compar方法。

代码

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

public class Solution {
    PriorityQueue<Integer> pqMax = new PriorityQueue<Integer>(new Comparator<Integer>(){
        @Override
        public int compare(Integer o1, Integer o2){
            return o2 - o1;
        }
    });
    PriorityQueue<Integer> pqMin = new PriorityQueue<Integer>();
    
    
    
    public void Insert(Integer num) {
        if(pqMax.size() == 0 || num < pqMax.peek()){
            pqMax.offer(num);
        }else{
            pqMin.offer(num);
        }
       if(Math.abs(pqMax.size() - pqMin.size()) > 1){
           if(pqMax.size() > pqMin.size()){
               pqMin.offer(pqMax.poll());
           }else{
               pqMax.offer(pqMin.poll());
           }
       }
    }

    public Double GetMedian() {
        int count = pqMax.size() + pqMin.size();
        if(count % 2 == 1){
            if(pqMax.size() > pqMin.size()){
                return 1.0 * pqMax.peek();
            }else{
                return 1.0 * pqMin.peek();
            }
        }else{
            return (pqMax.peek() + pqMin.peek())/2.0;
        }
    }
}

public class Solution {
    int count = 0;
    int[] arrMax = new int[10000];
    int[] arrMin = new int[10000];
    int left = 0;
    int right = 0;
    public void Insert(Integer num) {
        count++;
        if(num > arrMax[0]){
            //去小根堆
            arrMin[right] = num;//需上移
            heapifyMin(arrMin, right);
            right++;
        }else{
            //去大根堆
            arrMax[left] = num;//需上移
            heapifyMax(arrMax, left);
            left++;
        }
        
        if(Math.abs(right - left) > 1){
            if(left > right){
                arrMin[right] = arrMax[0];
                heapifyMin(arrMin, right++);
                swap(arrMax, 0, --left);
                heapifyMaxx(arrMax, left-1);
            }else{
                arrMax[left] = arrMin[0];
                heapifyMax(arrMax, left++);
                swap(arrMin, 0, --right);
                heapifyMinn(arrMin, right-1);
            }
        }
        
    }

    public Double GetMedian() {
        if(count % 2 == 1){
            if(left > right){
                return 1.0 * arrMax[0];
            }else{
                return 1.0 * arrMin[0];
            }
        }else{
            return (arrMax[0] + arrMin[0])/2.0;
        }
    }
    
    public void heapifyMax(int[] arr, int end){
        int index = end;
        int father = (end - 1)/2;
        while(father >= 0){
            if(arr[father] < arr[index]){
                swap(arr, father, index);
                index = father;
                father = (index - 1)/2;
            }else{
                break;
            }
        }
    }
    
    public void heapifyMin(int[] arr, int end){
        int index = end;
        int father = (end - 1)/2;
        while(father >= 0){
            if(arr[father] > arr[index]){
                swap(arr, father, index);
                index = father;
                father = (index - 1)/2;
            }else{
                break;
            }
        }
    }
    
    public void heapifyMaxx(int[] arr, int end) {
        int index = 0;
        int left = 2 * index + 1;
        while (left <= end) {
            int max = left + 1 <= end && arr[left + 1] > arr[left] ? left + 1: left;
            if(arr[max] > arr[index]){
                swap(arr, index, max);
                index = max;
                left = 2 * index + 1;
            }else{
                break;
            }
        }
    }
    
    public void heapifyMinn(int[] arr, int end){
        int index = 0;
        int left = 2 * index + 1;
        while (left <= end) {
            int min = left + 1 <= end && arr[left + 1] < arr[left] ? left + 1: left;
            if(arr[min] < arr[index]){
                swap(arr, index, min);
                index = min;
                left = 2 * index + 1;
            }else{
                break;
            }
        }
    }
    
    public void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}