存储来自数字流的最大5000个数字

Question

鉴于以下问题:

"从数字流中存储最大的5000个数字"

我们想到的解决方案是二进制搜索树,它保持树中节点数量的计数,以及一旦计数达到5000就对最小节点的引用.当计数达到5000时,可以将每个要添加的新数字进行比较树中最小的项目.如果更大,则可以添加新数字,然后移除最小的数字并计算新的最小数量(这应该非常简单,已经具有前一个最小值).

我对这个解决方案的关注是二叉树自然会出现偏差(因为我只是在一边删除).

有没有办法解决这个问题,不会造成一个非常歪斜的树？

如果有人想要它,我已经为我的解决方案包括伪代码到目前为止:

process(number)
{
  if (count == 5000 && number > smallest.Value)
  {
    addNode( root, number)
    smallest = deleteNodeAndGetNewSmallest ( root, smallest)
  }
}

deleteNodeAndGetNewSmallest( lastSmallest)
{
  if ( lastSmallest has parent)
  {
    if ( lastSmallest has right child)
    {
      smallest = getMin(lastSmallest.right)
      lastSmallest.parent.right = lastSmallest.right
    }
    else
    {
      smallest = lastSmallest.parent
    }
  }
  else 
  {
    smallest = getMin(lastSmallest.right)
    root = lastSmallest.right
  }
  count--
  return smallest
}

getMin( node)
{
  if (node has left)
    return getMin(node.left)
  else
    return node
}

add(number)
{
  //standard implementation of add for BST
  count++
}

Answer 1

最简单的解决方案是维持最大大小为5000 的最小堆.

• 每次有新号码到达时 - 检查堆是否小于5000,如果是 - 添加它.
• 如果不是 - 检查最小值是否小于新元素,如果是,则将其弹出并插入新元素.
• 完成后 - 你有一个包含5000个最大元素的堆.

这个解决方案很O(nlogk)复杂,其中n包含元素数量,k是您需要的元素数量(在您的情况下为5000).

它也可以在O(n)使用选择算法时完成 - 存储所有元素,然后找到第5001个最大元素,并返回比它大的所有元素.但实施起来比较困难并且合理的尺寸输入 - 可能不会更好.此外,如果流包含重复项,则需要更多处理.