在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
.
.
.

PS:使用此算法的一个示例可能是过滤图像.

Answer 1

好的,随着问题的更新,所以意图很明确(不只是找到中位数,而是每次收到一个新数字时重新找到中位数),我认为有一种方法.

我从一堆堆开始:最大堆和最小堆.min-heap将包含大于中位数的数字,max-heap包含小于中位数的数字.当你收到第一个号码时,那就是你的中位数.当您收到第二个时,将两个中较小的一个插入max-heap,将两个中较大的一个插入最小堆.中位数是最小堆上最小的平均值,最大堆上最大的平均值.

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

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

至少如果内存服务,提取/插入堆应该是O(log N).我相信所涉及的一切都应该是不变的复杂性.