从整数流中找出中位数

Question

给定一个未排序的整数序列,它作为流流入您的程序.

整数太多,不适合记忆.

想象一下有一个功能:

int getNext() throws NoSuchElementException;

它返回流中的下一个整数.

写一个函数来找到中位数.

解决O(n)中的问题.

有任何想法吗？

给出提示(使用堆数据结构..)

Answer 1

你必须保持两个堆一个最大堆(包含迄今为止看到的最小N/2个元素)和一个最小堆(包含最大的N/2个元素).如果N是奇数,则将额外元素存放在一边.

每当你调用函数getNext()时,

如果N变为奇数,则将新元素保存为额外元素.如有必要,将该元素与min-heap或max-heap中的元素进行交换,以满足以下条件

max(max-heap)<= extra element <= min(min-heap).

如果N变为偶数,则执行与上面相同的操作以获得第二个额外元素.然后,将较小的一个添加到max-heap,将较大的一个添加到min-heap.插入应为O(log N)

获得中位数:O(1)
如果N是奇数,则中位数是额外元素.
如果N是偶数,则中值是2个堆的顶部之间的平均值

Answer 2

请参阅本文。它（可能）需要不止一次通过。这个想法是，在每次传递中计算上限和下限，使得中位数位于它们之间。

这里的基本结果是N = 数据大小，P = 传递次数

定理2)选择N个元素中第K^个最高的P -pass算法最多需要存储O(N ^{( 1 / _P )} (logN) ^{( 2-2 / _P )} )。

此外，对于非常少量的存储S，即2 <= S <= O((log N) ² )，有一类选择算法最多使用O((log N) ^3/S )次。

阅读论文。我不太确定堆与它有什么关系