algorithm - 在 O(log n) 中找到中位数

Question

问题是我们如何在 O(log N) 中找到整数值接收流的中值(例如，对于 12、14、252、243、15，中值是 15)，其中N 是值的数量。请注意，我们有一个整数值流，因此通过接收每个值，我们必须重新找到中位数。

示例:

  | Input | median
1 |   12  |   12
2 |   14  |   13 = (12+14)/2
3 |   252 |   14
.
.
.

P.S:使用此算法的一个示例可以是过滤图像。

Answer 1

好的，随着问题的更新，意图很明确(不仅仅是找到中位数，而是每次收到新数字时重新找到中位数)，我认为有办法。

我将从一对堆开始:最大堆和最小堆。最小堆将包含大于中位数的数字，最大堆将包含小于中位数的数字。当您收到第一个数字时，这就是您的中位数。当您收到第二个时，将两者中较小的插入最大堆，将两者中较大的插入最小堆。中位数是最小堆上最小值和最大堆上最大值的平均值。

除了两个堆之外，您还需要存储一个整数，当您收到奇数个输入时，该整数将成为当前的中位数。你将相当简单地填充它:如果你收到一个当前已满的输入，你基本上对这两个项目(新数字和旧中位数)进行排序，并将较小的插入堆中以获取较小的项目，并将较大的插入堆中对于较大的元素。然后，您的新中位数将是这两个堆的基数的平均值(您会将另一个存储位置标记为空)。

当您收到一个空的新数字时，您会将新数字与中位数进行比较。如果它在作为堆底的数字之间，那就是新的中位数，你就完成了。否则，从必须保持中位数的基数中提取数字(如果新数字较大，则数字较大，如果新数字较小，则较小)并将其放入中位数点，然后将新数字插入来自的堆中。

至少如果内存可用，提取/插入堆应该是 O(log N)。我相信所涉及的其他一切都应该是不断复杂的。