我们可以使用两个优先队列（堆）维护所有的元素，第一个优先队列 small 是一个大根堆，它负责维护所有元素中较小的那一半；第二个优先队列 large 是一个小根堆，它负责维护所有元素中较大的那一半。具体地，如果当前需要维护的元素个数为 x，那么 small 中维护了 \lceil x}{2} \rceil 个元素，large 中维护了 \lfloor x}{2} \rfloor 个元素，其中 \lceil y \rceil 和 \lfloor y \rfloor 分别表示将 y 向上取整和向下取整。也就是说：
small 中的元素个数要么与 large 中的元素个数相同，要么比 large 中的元素个数恰好多 1 个。
这样设计的好处在于：当二者包含的元素个数相同时，它们各自的堆顶元素的平均值即为中位数；而当 small 包含的元素多了一个时，small 的堆顶元素即为中位数。这样 getMedian() 就设计完成了。
而对于 insert(num) 而言，如果当前两个优先队列都为空，那么根据元素个数的要求，我们必须将这个元素加入 small；如果 small 非空（显然不会存在 small 空而 large 非空的情况），我们就可以将 num 与 small 的堆顶元素 top 比较：
如果 num} \leq \textit{top，我们就将其加入 small 中；
如果 num} > \textit{top，我们就将其加入 large 中。
在成功地加入元素 num 之后，两个优先队列的元素个数可能会变得不符合要求。由于我们只加入了一个元素，那么不符合要求的情况只能是下面的二者之一：
small 比 large 的元素个数多了 2 个；
small 比 large 的元素个数少了 1 个。
对于第一种情况，我们将 small 的堆顶元素放入 large；对于第二种情况，我们将 large 的堆顶元素放入 small，这样就可以解决问题了，insert(num) 也就设计完成了。
deferase(self, num: int): self.delayed[num] += 1 if num <= -self.small[0]: self.smallSize -= 1 if num == -self.small[0]: self.prune(self.small) else: self.largeSize -= 1 if num == self.large[0]: self.prune(self.large) self.makeBalance()
classSolution: defmedianSlidingWindow(self, nums: List[int], k: int) -> List[float]: dh = DualHeap(k) for num in nums[:k]: dh.insert(num) ans = [dh.getMedian()] for i inrange(k, len(nums)): dh.insert(nums[i]) dh.erase(nums[i - k]) ans.append(dh.getMedian()) return ans
type hp struct { sort.IntSlice size int } func(h *hp) Push(v interface{}) { h.IntSlice = append(h.IntSlice, v.(int)) } func(h *hp) Pop() interface{} { a := h.IntSlice; v := a[len(a)-1]; h.IntSlice = a[:len(a)-1]; return v } func(h *hp) push(v int) { h.size++; heap.Push(h, v) } func(h *hp) pop() int { h.size--; return heap.Pop(h).(int) } func(h *hp) prune() { for h.Len() > 0 { num := h.IntSlice[0] if h == small { num = -num } if d, has := delayed[num]; has { if d > 1 { delayed[num]-- } else { delete(delayed, num) } heap.Pop(h) } else { break } } }
var delayed map[int]int var small, large *hp
funcmedianSlidingWindow(nums []int, k int) []float64 { delayed = map[int]int{} // 哈希表，记录「延迟删除」的元素，key 为元素，value 为需要删除的次数 small = &hp{} // 大根堆，维护较小的一半元素 large = &hp{} // 小根堆，维护较大的一半元素 makeBalance := func() { // 调整 small 和 large 中的元素个数，使得二者的元素个数满足要求 if small.size > large.size+1 { // small 比 large 元素多 2 个 large.push(-small.pop()) small.prune() // small 堆顶元素被移除，需要进行 prune } elseif small.size < large.size { // large 比 small 元素多 1 个 small.push(-large.pop()) large.prune() // large 堆顶元素被移除，需要进行 prune } } insert := func(num int) { if small.Len() == 0 || num <= -small.IntSlice[0] { small.push(-num) } else { large.push(num) } makeBalance() } erase := func(num int) { delayed[num]++ if num <= -small.IntSlice[0] { small.size-- if num == -small.IntSlice[0] { small.prune() } } else { large.size-- if num == large.IntSlice[0] { large.prune() } } makeBalance() } getMedian := func()float64 { if k&1 > 0 { returnfloat64(-small.IntSlice[0]) } returnfloat64(-small.IntSlice[0]+large.IntSlice[0]) / 2 }
for _, num := range nums[:k] { insert(num) } n := len(nums) ans := make([]float64, 1, n-k+1) ans[0] = getMedian() for i := k; i < n; i++ { insert(nums[i]) erase(nums[i-k]) ans = append(ans, getMedian()) } return ans }
voidswap(int* a, int* b) { int tmp = *a; *a = *b, *b = tmp; }
voidpush(struct Heap* obj, int x) { int p = ++(obj->heapSize), q = p >> 1; obj->heap[p] = x; while (q) { if (!obj->cmp(obj->heap[q], obj->heap[p])) { break; } swap(&(obj->heap[q]), &(obj->heap[p])); p = q, q = p >> 1; } }
voidpop(struct Heap* obj) { swap(&(obj->heap[1]), &(obj->heap[(obj->heapSize)--])); int p = 1, q = p << 1; while (q <= obj->heapSize) { if (q + 1 <= obj->heapSize) { if (obj->cmp(obj->heap[q], obj->heap[q + 1])) { q++; } } if (!obj->cmp(obj->heap[p], obj->heap[q])) { break; } swap(&(obj->heap[q]), &(obj->heap[p])); p = q, q = p << 1; } }
在 insert(num) 的过程中，如果我们将 insert(num) 放入了 large 中，并且 num 恰好出现在 large 的堆顶位置，且两个优先队列的元素个数满足要求，不需要进行调整。此时会不会出现 num 是一个需要被「延迟删除」的元素的情况，这样就不满足在 insert(num) 操作完成之后 large 的堆顶是不需要被「延迟删除」的要求了？
答案
是必要的。举个例子：在 insert(num) 操作之前，large 的堆顶元素是有效的，但其中第二小的元素是需要被删除的。此时，如果我们将一个很大的元素加入 large 中，并且 large 包含的元素数量超过了 small，那么我们就需要将 large 的堆顶元素放入 small 中。这样一来，large 的堆顶元素就变成了那个需要被删除的第二小的元素了，所以 prune(heap) 操作是必要的。
不可能会出现这种情况，假设出现了这种情况，那么 num 显然不会等于 large 原先的堆顶元素，因为 large 原先的堆顶元素一定是不需要被删除的。那么 num 满足：
