java - 有没有支持快速插入和中值计算的数据结构？

Question

这个问题已经有答案了:

How to calculate the median of an array? (16 个回答)

已关闭 3 年前。

我需要一个支持以下操作的数据结构:

1. 插入数字；
2. 求所有插入数字的中位数；
3. (附加)查找所有插入数字的预先已知分位数(0-1)；

最简单的方法是在每次插入后对数字进行排序，但这并不快。有没有更快的解决方案？

Answer 1

平衡二叉搜索树可以通过每个节点的子树的大小来扩展。在树旋转期间维护此统计数据是恒定时间的，您可以使用它来查找任意 i 值的 O(log N) 中的第 i 个元素:

• i < size(left) : 向左递归。
• i == size(left) :返回当前节点。
• i > size(left) :设置i = i - size(left) - 1并向右递归。

这样的数据结构将为所有三个操作提供 O(log N) 约束。