是否有数据结构支持快速插入和中位数计算？[重复]

Question

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

1. 插入一个数字;
2. 找到所有插入数字的中位数;
3. （附加）找到所有插入数字的已知分位数（0-1）;

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

Answer 1

好吧，如果您最初知道数组的内容开始排序，则可以使用此属性执行二进制搜索，以查找是否存在键，如果不存在，则应插入键的位置。然后，您可以在该点插入该值，数据将继续保持“已排序”。有点老派，是的，但它会很有效。

Answer 2

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

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

插入（x）：

• 如果数据结构中元素的计数为奇数（a存储中间元素，b不存储任何内容）：
  • 如果<代码>x
  • b=x
  • 如果 x
  • 将 x 放入 R 中
  • 将 a 放入 L
  • a = b
  • b = 空
  • 将 a 放入 L
  • 将 b 放入 R 中
  • a = x
  • b = 空

  GetMedian（）：

  • 只要返回a（如果元素计数为奇数）或（a、b）/2（元素计数为偶数）

Answer 3

平衡的二叉搜索树可以通过每个节点的子树的大小来增强。在树旋转期间，维护此统计信息是常数时间，您可以使用它来查找 o（log N） 中 i 的任何值的第 i 个元素：

• 我

这样的数据结构将在所有三个操作上给出O（logn）界。