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

Question

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

1. 插入一个数字；
2. 找出所有插入数字的中位数；
3. （附加）找到所有插入数字的预先知道的分位数（0-1）；

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

标签： javaalgorithmoptimizationdata-structures

Answer 1

您可以使用两个二进制堆在 O(logN) 中执行操作 (1) 和在 O(1) 中执行操作 (2)（也许您也可以快速执行操作 (3)，我只是不太熟悉概率论）。

创建一个 max-heapL和一个 min-heap R。创建两个变量a，b它们将存储一个（或两个）中间元素。堆L将存储所有小于中间元素的元素，堆R将存储所有大于中间元素的元素。L和的大小R将始终相同。

插入（x）：

• 如果数据结构中的元素计数是奇数（a存储中间元素，b不存储任何内容）：
  • 如果x < a：
    • b = a
    • a = x
  • 如果x >= a：
    • b = x
• 如果数据结构中的元素个数是偶数（a并b存储两个中间元素）：
  • 如果x < a：
    • 放入b_R
    • 放入x_L
    • b = null
  • 如果x > b：
    • 放入x_R
    • 放入a_L
    • a = b
    • b = null
  • 如果a <= x <= b：
    • 放入a_L
    • 放入b_R
    • a = x
    • b = null

获取中位数（）：

• 只需返回a（如果元素数为奇数）或(a + b) / 2（元素数为偶数）