Сохранить самые большие 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++
}