Moving Median

这是和Moving Average一样的一个统计学常用的方法. 这个比那个average更(有用).

用一个最大堆和一个最小堆维护. 先往最小堆里放第一个元素, 然后其他元素就比一下, 如果比最小堆的顶元素小或者等于, 就放最小堆,不是就放最大堆. 然后还需要一个rebalance的方法, 如果其中一个堆比另一个堆多一个以上,就扔过去一个.

import java.util.Collections;
import java.util.PriorityQueue;

/**
 * Created by Chenguang He ([email protected]) on 10/5/15.
 */
public class MovingMedian {
    private PriorityQueue<Integer> minHeap = new PriorityQueue<>(Collections.reverseOrder());
    private PriorityQueue<Integer> maxHeap = new PriorityQueue<>();

    public void add(Integer i) {
        if (minHeap.isEmpty() && maxHeap.isEmpty())
            minHeap.add(i);
        else {
            if (i <= minHeap.peek())
                minHeap.add(i);
            else
                maxHeap.add(i);
            rebalance();
        }
    }

    private void rebalance(){
        if (minHeap.size() < maxHeap.size()-1) {
            minHeap.add(maxHeap.remove());
        }
        else if (minHeap.size() > maxHeap.size() +1){
            maxHeap.add(minHeap.remove());
        }
    }

    public float getMedian(){
        if (minHeap.size() == 0 && maxHeap.size() == 0)
            return -1;
        else if (minHeap.size() == maxHeap.size())
            return (float)(minHeap.peek()+maxHeap.peek())/(float)2;
        else
            return (minHeap.size() < maxHeap.size()) ? maxHeap.peek():minHeap.peek();
    }

    public static void main(String[] args) {
        int[] t = new int[]{4,-2,1,2,-3};
        MovingMedian m = new MovingMedian();
        for (int tt : t)
            m.add(tt);
        System.out.println(m.getMedian());
    }
}