从数字流存储最多5000号从数字流存储最多5000号(Store the largest 5000

考虑下面的问题：

“从数字流存储最大的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)使用选择算法存储的所有元素，然后找到5001th最大的元素，并返回一切比它更大- 。但是这是很难实现和合理的尺寸输入 - 可能不是更好。此外，如果流包含重复，需要更多的处理。

Answer 2:

使用（最低）优先级队列。每个进入的项目添加到队列中，每次添加一个传入元素的时候大小达到5000取消最低（最高）元素。队列将包含5000个最大元素和输入停止时，只是删除的内容。这MinPQ也被称为堆但这是一个重载的术语。插入和缺失约需LOG2（N）。其中N在5000马克塞斯这将是刚刚超过12 [LOG2（4096）= 12]要处理项目的次数。

信息的最佳来源是算法，（第4版）由罗伯特·塞奇威克和凯文·韦恩。有上coursera.org一个很好的MOOC是基于这个文本。

文章来源: Store the largest 5000 numbers from a stream of numbers