Almacena los 5000 números más grandes de un flujo de números

Dado el siguiente problema:

"Almacena los 5000 números más grandes de un flujo de números"

La solución que viene a la mente es un árbol de búsqueda binario que mantiene un recuento del número de nodos en el árbol y una referencia al nodo más pequeño una vez que el recuento llega a 5000. Cuando el recuento llega a 5000, cada número nuevo que se agrega se puede comparar con El elemento más pequeño en el árbol. Si es mayor, se puede agregar el nuevo número, luego se eliminará el más pequeño y se calculará el nuevo más pequeño (que debería ser muy simple, ya que tiene el más pequeño anterior).

Mi preocupación con esta solución es que, naturalmente, el árbol binario se va a desviar (ya que solo estoy eliminando de un lado).

¿Hay una manera de resolver este problema que no cree un árbol terriblemente sesgado?

En caso de que alguien lo desee, he incluido un pseudo-código para mi solución hasta ahora:

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++
}

Respuestas a la pregunta(2)

Su respuesta a la pregunta