数据流/滑动窗口中位数

type Cmp func(int, int) bool

type Heap struct {
	slice []int
	cmp   Cmp
}

// implement heap.Interface
func (h *Heap) Len() int           { return len(h.slice) }
func (h *Heap) Less(i, j int) bool { return h.cmp(h.slice[i], h.slice[j]) }
func (h *Heap) Swap(i, j int)      { h.slice[i], h.slice[j] = h.slice[j], h.slice[i] }
func (h *Heap) Push(x interface{}) { h.slice = append(h.slice, x.(int)) }
func (h *Heap) Pop() interface{} {
	x := h.slice[h.Len()-1]
	h.slice = h.slice[:h.Len()-1]
	return x
}
// local functions
func (h *Heap) push(x int) { heap.Push(h, x) }
func (h *Heap) pop() int   { return heap.Pop(h).(int) }
func (h *Heap) peek() int  { return h.slice[0] }

type MedianFinder struct {
	small, large *Heap
}

func Constructor() MedianFinder {
	res := MedianFinder{&Heap{}, &Heap{}}
	res.small.cmp = func(a, b int) bool {
		return a > b
	}
	res.large.cmp = func(a, b int) bool {
		return a < b
	}
	return res
}

func (mf *MedianFinder) AddNum(num int) {
	if mf.small.Len() == 0 || num <= mf.small.peek() {
		mf.small.push(num)
	} else {
		mf.large.push(num)
	}
	mf.makeBalance()
}

func (mf *MedianFinder) makeBalance() {
	if mf.small.Len() > mf.large.Len()+1 {
		mf.large.push(mf.small.pop())
	} else if mf.small.Len() < mf.large.Len() {
		mf.small.push(mf.large.pop())
	}
}

func (mf *MedianFinder) FindMedian() float64 {
	if mf.small.Len() > mf.large.Len() {
		return float64(mf.small.peek())
	}
	if mf.large.Len() == 0 && mf.small.Len() == 0 {
		return 0
	}
	return float64(mf.small.peek()+mf.large.peek()) * 0.5
}

func medianSlidingWindow(nums []int, k int) []float64

func medianSlidingWindow(nums []int, k int) []float64 {
	mf := NewMedianFinder()
	res := make([]float64, 0, len(nums)-k+1)
	for i, v := range nums {
		mf.Put(v)
		if i >= k-1 {
			res = append(res, mf.FindMedian())
			mf.Remove(nums[i-k+1])
		}
	}
	return res
}

type MedianFinder struct {
	left, right *Heap
}

func NewMedianFinder() *MedianFinder {
	return &MedianFinder{
		left:  &Heap{cmp: func(x, y int) bool { return x > y }, memo: map[int]int{}},
		right: &Heap{cmp: func(x, y int) bool { return x < y }, memo: map[int]int{}},
	}
}

func (mf *MedianFinder) Put(num int) {
	mf.left.push(num)
	mf.right.push(mf.left.pop())
	mf.makeBalance()
}
func (mf *MedianFinder) Remove(x int) {
	if mf.left.size > 0 && mf.left.peek() >= x {
		mf.left.remove(x)
	} else {
		mf.right.remove(x)
	}
	mf.makeBalance()
}

func (mf *MedianFinder) makeBalance() {
	// 注意这里用size而不是Len()
	if mf.left.size > mf.right.size+1 {
		mf.right.push(mf.left.pop())
	} else if mf.left.size < mf.right.size {
		mf.left.push(mf.right.pop())
	}
}

func (mf *MedianFinder) FindMedian() float64 {
	if mf.left.size > mf.right.size {
		return float64(mf.left.peek())
	}
	return float64(mf.left.peek()+mf.right.peek()) / 2
}

type Heap struct {
	items []int
	cmp   func(int, int) bool
	memo  map[int]int // 记录应该删除的元素
	size  int         // 记录堆预期的大小，因为删除延迟的原因，堆的实际大小(items的大小)并非预期大小
}

func (h *Heap) Len() int           { return len(h.items) }
func (h *Heap) Less(i, j int) bool { return h.cmp(h.items[i], h.items[j]) }
func (h *Heap) Swap(i, j int)      { h.items[i], h.items[j] = h.items[j], h.items[i] }
func (h *Heap) Push(x interface{}) { h.items = append(h.items, x.(int)) }
func (h *Heap) Pop() interface{} {
	n := len(h.items)
	res := h.items[n-1]
	h.items = h.items[:n-1]
	return res
}

// push 向堆里添加一个元素
func (h *Heap) push(x int) {
	h.clean()
	h.size++
	heap.Push(h, x)
}

// pop 删除堆顶元素并返回其值
func (h *Heap) pop() int {
	h.clean()
	h.size--
	return heap.Pop(h).(int)
}

// peek 获取堆顶元素
func (h *Heap) peek() int {
	h.clean()
	return h.items[0]
}

// remove 在堆里删除元素 num
func (h *Heap) remove(x int) {
	h.clean()
	h.size--
	h.memo[x]++
}

// 循环检查堆顶元素，如果在 memo 缓存中则删除
func (h *Heap) clean() {
	for len(h.items) > 0 && h.memo[h.items[0]] > 0 {
		h.memo[h.items[0]]--
		heap.Pop(h)
	}
}

type Heap struct {
	cmp  Comparator
	data []int
	idx  map[int]int // 维护每个元素在 data 数组中的索引
	cnt  map[int]int // 可能有多个相同元素入堆，我们仅在 data 中维护去重后的元素，cnt 维护每个元素的个数
	size int         // size 维护堆的总大小，这个值大于等于 len(data)
}

type Comparator func(a, b int) bool

func New(cmp Comparator) *Heap {
	return &Heap{
		data: make([]int, 0),
		idx:  make(map[int]int),
		cnt:  make(map[int]int),
		cmp:  cmp,
	}
}

// for stantard heap package ====
func (h *Heap) Len() int           { return len(h.data) }
func (h *Heap) Less(i, j int) bool { return h.cmp(h.data[i], h.data[j]) }
func (h *Heap) Swap(i, j int) {
	h.data[i], h.data[j] = h.data[j], h.data[i]
	h.idx[h.data[i]] = i
	h.idx[h.data[j]] = j
}
func (h *Heap) Push(x interface{}) { h.data = append(h.data, x.(int)) }
func (h *Heap) Pop() interface{} {
	n := len(h.data)
	res := h.data[n-1]
	h.data = h.data[:n-1]
	return res
}

// === end

func (h *Heap) push(x int) {
	if h.cnt[x] == 0 {
		h.idx[x] = len(h.data)
		heap.Push(h, x)
	}
	h.cnt[x]++
	h.size++
}
func (h *Heap) pop() int {
	res := h.data[0]
	if h.cnt[res] == 1 {
		heap.Pop(h)
		h.idx[res] = -1
	}
	h.cnt[res]--
	h.size--
	return res
}
func (h *Heap) peek() int {
	return h.data[0]
}
func (h *Heap) remove(x int) int {
	if h.cnt[x] == 1 {
		heap.Remove(h, h.idx[x])
		h.idx[x] = -1
	}
	h.size--
	h.cnt[x]--
	return x
}