找到中位数的数据结构

Question

这是一个面试问题。设计一个类，它存储整数并提供两个操作：

void insert(int k)
int getMedian()

我想我可以使用BST，以便插入取O（logN）和getMedian取O（logN）（对于getMedian我应该添加每个节点的左/右子节点的数量）。

现在我想知道这是否是最有效的解决方案，没有更好的解决方案。

Answer 1

如果您在O中选择候选者，它会击败整数数组吗？女巫会在插入时使用专用于整数（http://en.wikipedia.org/wiki/Sorting_algorithm）的排序算法执行排序

此外，通过更灵活一点，您可以通过根据输入的属性更改排序算法来提高性能（输入是否几乎排序...）。

我在计算机科学方面几乎是自学成才的，但这就是我的做法：简单越好。

Answer 2

有关涉及两个堆的解决方案，请参见此堆栈溢出问题。

Answer 3

您可以使用2堆，我们将调用左和右。
左是Max-Heap。
右是Min-Heap。
插入是这样完成的：

• 如果新元素x小于左的根，那么我们将x插入左。
• 否则我们将x插入right。
  
• 如果插入左后的元素计数大于右的元素计数的1，那么我们在左上调用Extrac-Max并将其插入到右。
• 否则，如果插入右后的元素计数大于左的元素计数，则我们在右上调用Extract-Min并将其插入到左。

中位数始终是左的根。

因此，插入是在O（lg n）时间内完成的，而中位数是在O（1）时间内完成的。