data-structures - 寻找中位数的数据结构

Question

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

无效插入（int k）
整数 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 onLeft并将其插入到Right。
• 否则，如果插入后Right的元素计数大于 的元素计数Left，则我们调用 Extract-MinRight并将其插入到Left。

中位数始终是 的根Left。

所以插入是O(lg n)及时完成的​​，并且得到中位数是O(1)及时完成的​​。

Answer 2

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

Answer 3

如果你在 O < O(log(n) 中选择你的候选人，它会打败一个整数数组吗？ ) 并使用一个数组，那么 getMedian 将采用一半大小的索引是 O(1)，不是吗？在我看来，比 log(n) + log(n) 做得更好。

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

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

Answer 4

您也可以考虑使用自平衡树。如果树是完全平衡的，那么根节点就是你的中位数。比如说，树的一端更深一层。然后，您只需要知道更深的一侧有多少个节点即可选择正确的中位数。