题解 | #数据流中的中位数#

package main

import "container/heap"

var minArray minHeap
var maxArray maxHeap

func Insert(num int){
	//小顶堆存值更大的一半数，大顶堆存值更小的一半数，保证大顶堆的数全部比小顶堆的小
	heap.Init(&minArray)
	heap.Init(&maxArray)
	// 优先放在大顶堆；奇数的时候，大顶堆比小顶堆数据多1
	if maxArray.Len() <= minArray.Len() {
		// 需要插入的数据比小顶堆的最小值还小，可以直接插入大顶堆
		if num < minArray.Top() {
			heap.Push(&maxArray, num)
		} else {
			// 需要插入的数据比小顶堆的最小值大，先取出小顶堆的最小值插入大顶堆，再将目标数插入小顶堆
			heap.Push(&maxArray, heap.Pop(&minArray))
			heap.Push(&minArray, num)
		}
	} else {
		// 与上同理
		if num < maxArray.Top() {
			heap.Push(&minArray, heap.Pop(&maxArray))
			heap.Push(&maxArray, num)
		} else {
			heap.Push(&minArray, num)
		}
	}
	return
}

func GetMedian() float64{
	if maxArray.Len() > minArray.Len() {
		return float64(maxArray.Top())
	}
	return (float64(maxArray.Top()) + float64(minArray.Top())) / 2
}

type minHeap []int

func (h minHeap) Top() int {
	if len(h) == 0 {
		return 1 << 32-1
	}
	return h[0]
}

func (h *minHeap) Pop() interface{} {
	if len(*h) == 0 {
		return nil
	}
	ret := (*h)[len(*h)-1]
	*h = (*h)[:len(*h)-1]
	return ret
}

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

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]
	return
}

type maxHeap []int

func (h maxHeap) Top() int {
	if len(h) == 0 {
		return -1
	}
	return h[0]
}

func (h *maxHeap) Pop() interface{} {
	if len(*h) == 0 {
		return nil
	}
	ret := (*h)[len(*h)-1]
	*h = (*h)[:len(*h)-1]
	return ret
}

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

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]
	return
}