动态维护中位数应选对顶堆或带size的平衡BST：对顶堆稳快省，适合仅需中位数；平衡BST扩展性强，支持任意分位数查询。

动态维护中位数，核心在于“边加边查、不重排”，二叉搜索树（BST）能做，但直接用原生BST有风险——它可能退化成链表，导致单次操作从O(log n)掉到O(n)。真正实用的方案，是结合BST思想+平衡机制，或换用更稳健的组合结构。

为什么纯BST在流式场景中容易翻车

中位数依赖数据的有序分布：一半数 ≤ 中位数，一半数 ≥ 中位数。BST天然支持按序组织，理论上插入、查找中位数都能摊到O(log n)。但问题出在数据分布上：

• 若数据流本身接近有序（如时间戳递增、ID连续），BST会快速变成右倾长链，高度≈n，每次查找中位数需遍历近半节点
• 中位数位置随数量奇偶动态变化：n为奇数时取第(n+1)/2小元素；n为偶数时需取第n/2和第n/2+1小元素的平均值——这要求BST能快速定位任意排名（rank）的元素
• 标准BST不存子树节点数，找第k小必须中序遍历计数，退化为O(n)

可行解法一：带size字段的平衡BST（如AVL或红黑树）

给每个节点增加size字段，记录以该节点为根的子树总节点数。这样就能像“二分索引”一样跳转定位第k小：

• 设当前节点左子树大小为left_size，若k ≤ left_size → 向左子树找第k小
• 若k == left_size + 1 → 当前节点即为第k小
• 若k > left_size + 1 → 向右子树找第(k − left_size − 1)小

插入/删除时同步更新路径上所有祖先的size值。C++ STL中的pb_ds库、Java的TreeSet配合自定义rank逻辑，或手写AVL+size，都可支撑O(log n)中位数查询。

可行解法二：对顶堆——更轻量、更常用

不用树，用两个堆更直接：

• 大根堆（max-heap）存较小的一半，堆顶是这一半的最大值
• 小根堆（min-heap）存较大的一半，堆顶是这一半的最小值
• 始终维持：|大根堆.size − 小根堆.size| ≤ 1

中位数直接由堆顶决定：总数奇数→多出那个堆的堆顶；总数偶数→两堆顶平均。每次插入O(log n)，查询O(1)，无退化风险，代码简洁，工业界实时监控系统（如Flink指标聚合）常用此法。

实际选型建议

看需求侧重点：

• 只要中位数，不要其他排名（如Top5、P95）→ 优先用对顶堆，稳、快、省
• 既要中位数，又要任意分位数、区间统计、历史回溯→ 上平衡BST（如红黑树+size），扩展性强
• 已有成熟库支持（如C++的__gnu_pbds::tree、Python的sortedcontainers.SortedList）→ 可直接封装为中位数服务，避免手写平衡逻辑