11

鉴于以下问题：

“存储数字流中最大的 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++
}
4

2 回答 2

38

最简单的解决方案是维护一个最大大小为 5000 的最小堆。

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

这个解决方案很O(nlogk)复杂，其中n元素的数量是元素的数量，并且k是您需要的元素数量（在您的情况下为 5000）。

也可以O(n)使用选择算法来完成- 存储所有元素，然后找到第 5001 个最大的元素，并返回大于它的所有元素。但它更难实现和合理的大小输入 - 可能不会更好。此外，如果流包含重复项，则需要更多处理。

于 2012-05-25T09:36:49.443 回答
1

使用（最低）优先级队列。将每个传入项目添加到队列中，当大小达到 5,000 时，每次添加传入元素时删除最小（顶部）元素。队列将包含 5,000 个最大的元素，当输入停止时，只需删除内容。此 MinPQ 也称为堆，但这是一个重载术语。插入和删除大约需要 log2(N)。其中 N 最大值为 5,000，这将是您正在处理的项目数的 12 [log2(4096) = 12] 倍。

一个极好的信息来源是 Robert Sedgewick 和 Kevin Wayne 的 Algorithms，（第 4 版）。coursera.org 上有一个基于此文本的优秀 MOOC。

于 2013-11-01T16:31:03.133 回答