维基百科说:
选择算法:使用堆可以在线性时间内完成最小值,最大值,最小值和最大值,中值或甚至第k个最大元素的查找.
它说的只是它可以完成,而不是如何完成.
你能给我一些关于如何使用堆来完成这项工作的开始吗？
我试图了解分布式计算,并遇到了一个查找大量数字中位数的问题:
假设我们有一大组数字(假设元素数量是N*K),它们不能适合内存(大小为N).我们如何找到这些数据的中位数？假设在存储器上执行的操作是独立的,即我们可以认为每个K机器最多可以处理N个元素.
我认为中位数的中位数可用于此目的.我们可以一次将N个数字加载到内存中.我们O(logN)及时找到该集合的中位数并保存.
然后我们保存所有这些K中位数并找出中位数的中位数.此外O(logK),到目前为止,复杂性一直是O(K*logN + logK).
但这个中位数的中位数只是一个近似的中位数.我认为将它用作获得最佳案例性能的支点是最佳的,但为此我们需要将所有N*K数字拟合到内存中.
现在我们有一个很好的近似支点,我们怎样才能找到集合的实际中位数？
这是StackOverflow 问题的衍生产品.
假设您有一个固定数量k的存储位置,以及两个计数器的空间.您将收到ñ随机顺序的项目(的所有排列ň项目也同样可能).收到每个项目后,您可以将其存储在k个位置之一(丢弃之前存储的值之一),或丢弃该项目.您也可以递增或递减任一计数器.无法检索任何丢弃的项目.
问题是
显然,如果k> n/2,我们可以找到中位数.一般来说,试图保持丢弃的高值的数量等于丢弃的低值的数量的相同策略应该是最佳的,但我不确定如何证明它,也不知道如何找出它找到的概率中位数.
同样感兴趣的是我们不知道的情况下ñ但要知道的概率分布ñ.
编辑: 现在假设值是不同的(没有重复.)但是,如果你也可以解决非独特的情况,那将是令人印象深刻的.