data-structures - 求中位数的数据结构

Question

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

空插入(int k)
int getMedian()

我想我可以使用 BST 以便 insert取 O(logN) 和 getMedian需要 O(logN)(对于 getMedian 我应该为每个节点添加左/右 child 的数量)。

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

Answer 1

您可以使用 2 个堆，我们称之为 Left和 Right .Left是 Max-Heap .Right是 Min-Heap .
插入是这样完成的:

如果新元素x小于 Left 的根然后我们插入 x至 Left .

否则我们插入 x至 Right .

如果插入后Left从 Right 的元素计数中具有大于 1 的元素计数，然后我们在 Left 上调用 Extract-Max并将其插入 Right .

否则如果插入后 Right具有大于 Left 的元素计数的元素计数，然后我们在 Right 上调用 Extract-Min并将其插入 Left .

中位数始终是 Left 的根.

所以插入是在 O(lg n) 中完成的时间和获取中位数在 O(1) 中完成时间。