数据流中的中位数

数据流中的中位数

剑指 Offer 41. 数据流中的中位数

class MedianFinder {
public:
    /** initialize your data structure here. */
    
    //大顶堆 存较小值
    priority_queue<int> min_pq;
    //小根堆 存较大值
    priority_queue<int, vector<int>, greater<int>> max_pq;

    MedianFinder() {

    }
    
    void addNum(int num) {
        //先加入到较小值部分
        min_pq.push(num);
        //将较小值中最大值 移入较大值部分
        max_pq.push(min_pq.top());
        min_pq.pop();
        //平衡数量
        if(min_pq.size() < max_pq.size()){
            min_pq.push(max_pq.top());
            max_pq.pop();
        }
    }
    
    double findMedian() {
        //奇数个数
        if(min_pq.size()>max_pq.size()){
            return (double)min_pq.top();
        }else{//偶数个数
            return (double)(min_pq.top()+max_pq.top())/2;
        }
    }
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */

type MedianFinder struct {
    // 大顶堆 存较小值
    minHeap *MaxHeap
    // 小根堆 存较大值
    maxHeap *MinHeap
}

// 大顶堆实现
type MaxHeap []int

func (h MaxHeap) Len() int           { return len(h) }
func (h MaxHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h MaxHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *MaxHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}

func (h *MaxHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

// 小根堆实现
type MinHeap []int

func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *MinHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}

func (h *MinHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

/** initialize your data structure here. */
func Constructor() MedianFinder {
    minHeap := &MaxHeap{}
    maxHeap := &MinHeap{}
    heap.Init(minHeap)
    heap.Init(maxHeap)
    return MedianFinder{
        minHeap: minHeap,
        maxHeap: maxHeap,
    }
}

func (this *MedianFinder) AddNum(num int) {
    // 先加入到较小值部分
    heap.Push(this.minHeap, num)
    // 将较小值中最大值 移入较大值部分
    heap.Push(this.maxHeap, heap.Pop(this.minHeap))
    // 平衡数量
    if this.minHeap.Len() < this.maxHeap.Len() {
        heap.Push(this.minHeap, heap.Pop(this.maxHeap))
    }
}

func (this *MedianFinder) FindMedian() float64 {
    // 奇数个数
    if this.minHeap.Len() > this.maxHeap.Len() {
        return float64((*this.minHeap)[0])
    } else { // 偶数个数
        return float64((*this.minHeap)[0]+(*this.maxHeap)[0]) / 2.0
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * obj := Constructor();
 * obj.AddNum(num);
 * param_2 := obj.FindMedian();
 */