Przechowuj największe liczby 5000 ze strumienia liczb

Biorąc pod uwagę następujący problem:

"przechowuj największe 5000 liczb ze strumienia liczb"

Rozwiązaniem, które przychodzi na myśl, jest binarne drzewo wyszukiwania utrzymujące liczbę węzłów w drzewie i odniesienie do najmniejszego węzła, gdy liczba osiągnie 5000. Gdy liczba osiągnie 5000, każda nowa Liczba do dodania może być porównana z najmniejszym elementem w drzewie. Jeżeli jest większa, można dodać nową liczbę, wtedy najmniejsza usunięta i nowa najmniejszy obliczony (który powinien być bardzo prosty już mając poprzedni najmniejszy).

Mój problem z tym rozwiązaniem polega na tym, że drzewo binarne naturalnie zostanie wypaczone (ponieważ usuwam tylko z jednej strony).

Czy istnieje sposób na rozwiązanie tego problemu, który nie stworzy strasznie przekrzywionego drzewa?

W razie gdyby ktoś chciał, umieściłem pseudo-kod dla mojego rozwiązania do tej pory poniżej:

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