数据结构寻找中位数

Question

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

void insert(int k)
int getMedian()

我猜可以使用二叉搜索树（BST）来实现，使得 insert 的时间复杂度为 O(logN)，getMedian 的时间复杂度也为 O(logN)（对于getMedian，需要为每个节点添加其左/右子节点的数量）。

现在我想知道是否有更高效的解法，是否存在更优秀的算法。

- Michael

---

使用你的方案，可以将 getMedian 改进到 O(1)：每次插入后查找中位数（这不会影响复杂度），并将其存储起来。 - Steve Jessop

考虑使用优先队列来替代当前的结构。 - Steve Jessop

@SteveJessop，您能否详细说明如何将getMedian改进为O(1)？ - Michael

我的意思是你的数据结构应该有一个数据成员 int currentMedian;。在将元素插入二叉搜索树后，立即找到新的中位数，并将该值存储到 currentMedian 中，然后再从 insert 函数返回。然后你可以实现 int getMedian() { return currentMedian; }，这样时间复杂度为 O(1)。 - Steve Jessop

进一步思考后，您可能也可以使用跳表来实现。这样可以在预期/平摊的O(log(n))时间内进行插入，并且可以跟踪中位数节点（以及元素数量是奇数还是偶数）。每次插入时，您只需要检查是否根据旧中位数的左侧或右侧插入以及新大小是奇数还是偶数来将中位数向左或向右移动一步即可。 - Steve Jessop

Answer 1

您可以使用两个堆，我们将其称为左堆和右堆。
左堆是一个最大堆。
右堆是一个最小堆。
插入操作如下：

• 如果新元素x小于左堆的根节点，则将x插入到左堆。
• 否则，将x插入到右堆。
  
• 如果插入后左堆的元素数量比右堆的元素数量多1，则从左堆中提取最大值并将其插入到右堆中。
• 否则，如果插入后右堆的元素数量比左堆的元素数量多，则从右堆中提取最小值并将其插入到左堆中。

中位数始终是左堆的根节点。

因此，插入操作的时间复杂度为O(lg n)，获取中位数的时间复杂度为O(1)。

- Avi Cohen

---

太好了，这是我的cpp实现：https://gist.github.com/jonnyhsy/7ec9546a3622cf575b82 - nrek

如果有人需要一个还能够实现删除的实现，我已经扩展了由@Amit链接的解决方案 https://gist.github.com/JernejJerin/a26276d2289878bd7744 - Jernej Jerin

@JernejJerin，您能否简要解释一下您的删除功能是如何工作的？ - Hengameh

感谢澄清。所以，删除的时间复杂度是O(n)。 :) - Hengameh

这个想法是正确的，但有一个小问题：建议的解决方案假设数字的数量是偶数。中位数的数学定义也包括数字数量为奇数的情况。来自维基百科的定义如下：如果观测值的数量是偶数，则没有单个中间值；中位数通常被定义为两个中间值的平均值（https://en.wikipedia.org/wiki/Median）。 - Ron Klein

Answer 2

请参考这个Stack Overflow问题，其中提供了使用两个堆的解决方案。

- user448810

Answer 3

如果您在插入时使用专门用于整数的排序算法（http://en.wikipedia.org/wiki/Sorting_algorithm），并从O < O(log(n))中选择候选项，并使用数组，则它是否能够击败执行排序的整数数组，然后获取中位数将取一半大小的索引将是O(1)，不是吗？我觉得可能比log(n) + log(n)更好。

此外，通过更加灵活，根据输入的属性（输入是否几乎排序或不排序等）更改排序算法，可以提高性能。

我在计算机科学方面基本上是自学成才，但这就是我会做的方式：简单就是更好。

- user1458574

---

对于大数据，这种方法会受到insert是O(n)的影响，但如果存储的值的数量很少，这可能是最好的方法。 - Steve Jessop

是的，它被隐藏在笔记中 :)（我希望没有人注意到）。 在实际编码中，最佳实现仍然取决于上下文^^。因此，我认为最佳实现的理论问题就像试图以简单数字的形式告诉函数的最小值，而你的函数是参数化的。 - user1458574

Answer 4

你可以考虑使用自平衡树。如果树完全平衡，那么根节点就是中位数。假设树的一端比另一端深一层，那么你只需要知道深层端有多少个节点，就能选择正确的中位数了。

- grdvnl

---

假设你的平衡度最大的树有偶数个节点，则中位数是两个值的平均数。其中一个值是根节点，另一个值深藏在树的 (log n) 层深处，因为它是右子树的最左边节点或者左子树的最右边节点。因此，为了以 O(1) 的时间访问中位数，您需要追踪的不仅仅是根节点和子树的大小，但仅靠根节点就足以实现 O(log n) 时间复杂度。 - Steve Jessop

@SteveJessop，您能否举几个例子，其中中位数是“右子树最左节点和根节点的平均值”的情况？我尝试的每个样本中，中位数都是左子树最右节点和根节点的平均值！ - Hengameh

@Hengameh：考虑一个由两个节点组成的树：根节点和其右子节点。那么右子节点是右子树中最左边的节点，而中位数是该节点与根节点的平均值。 - Steve Jessop