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

您可以使用选择算法查找前k个元素，但通过存储2k个元素的数组仅使用O（k）内存。每次填充数组时，请使用选择算法删除最低的k。不管k的值如何，这都会花费O（n）时间，因为您正在执行O（n / k）选择算法，每个算法都花费时间O（k）。它还仅使用O（k）内存。