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