题目定位
中位数天然位于下半部分和上半部分之间，因此“大根堆 + 小根堆”是最标准的结构。
关键观察
一个堆维护较小的一半，一个堆维护较大的一半，两者大小差不能超过 1。
目标复杂度
O(log n) / O(n)
这题的解法思路怎么拆
1
中位数天然位于下半部分和上半部分之间，因此“大根堆 + 小根堆”是最标准的结构。
2
一个堆维护较小的一半，一个堆维护较大的一半，两者大小差不能超过 1。
3
先用一句话说明堆顶代表什么。
4
新候选者一旦合格就立刻入堆。
参考实现
Python# Generic pattern template
import heapq
heap = []
heapq.heappush(heap, value)
smallest = heapq.heappop(heap)
# max heap in Python
heapq.heappush(heap, -value)
largest = -heapq.heappop(heap)
常见坑点
warning
插入后忘了重新平衡两个堆。
warning
元素个数为奇数时，没有统一约定哪边多一个。
高频追问
两个堆之间必须长期维持什么不变式？
为什么每次都整体排序不现实？
继续刷相关题
先把 堆 / 优先队列 这个模式刷成体系，再去做更难变体。