中位数

GitHub跳转原题关系图返回列表

最大堆和最小堆维护前缀的较小一半与较大一半，奇数长度输出最大堆顶。

OJ: luogu

题目 ID: P1168

难度:普及/提高-

标签:双堆中位数heapqpython

日期: 2026-07-16 21:00

目录

  1. 题意
  2. 思路
  3. Python 知识
  4. 代码
  5. 复杂度
  6. 总结

题意

依次读入序列，对每个奇数长度前缀输出中位数。

思路

lower 负数最大堆保存较小一半，upper 小根堆保存较大一半。每次插入后调整到 len(lower) 等于或比 upper 多 1，奇数长度时中位数就是 -lower[0]。

Python 知识

  • -value 是 Python 3.14 以前通用的最大堆写法。
  • enumerate 的偶数下标对应已读奇数个元素。
  • 两个 heappop/heappush 完成跨堆再平衡。

代码

python
import heapq
import sys


data = iter(map(int, sys.stdin.buffer.read().split()))
n = next(data)
lower = []
upper = []
answers = []

for index in range(n):
    value = next(data)
    if not lower or value <= -lower[0]:
        heapq.heappush(lower, -value)
    else:
        heapq.heappush(upper, value)
    if len(lower) > len(upper) + 1:
        heapq.heappush(upper, -heapq.heappop(lower))
    elif len(upper) > len(lower):
        heapq.heappush(lower, -heapq.heappop(upper))
    if index % 2 == 0:
        answers.append(str(-lower[0]))

print("\n".join(answers))

复杂度

每项 O(log⁡n)O(\log n)，空间 O(n)O(n)。

总结

动态中位数的本质是维持有序序列在中点处的两半，而不是每次重新排序。