数据结构找到中位数

Question

这是一个面试问题.设计一个类,它存储整数并提供两个操作:

void insert(int k)
int getMedian()

我想我可以使用BST,因此insert需要O(logN)并getMedian取O(logN)(因为getMedian我应该为每个节点添加左/右子节点的数量).

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

Answer 1

您可以使用2堆,我们将调用Left和Right.
Left是一个Max-Heap.
Right是一个Min-Heap.
插入是这样完成的:

• 如果新元素x比根小Left然后我们插入x到Left.
• 否则,我们插入x到Right.
  
• 如果插入后Left的元素数量大于1的元素数Right,则我们调用Extract-Max Left并将其插入Right.
• 否则,如果插入后Right的元素数大于元素数Left,则我们调用Extract-Min Right并将其插入Left.

中位数始终是根的Left.

因此,O(lg n)及时完成插入并及时完成中位数O(1).

Answer 2

请参阅此Stack Overflow 问题，了解涉及两个堆的解决方案。