Armazene os maiores 5000 números de um stream de números

Dado o seguinte problema:

“Armazene os maiores 5000 números de um stream de números”

A solução que vem à mente é uma tree de pesquisa binária que mantém uma contagem do número de nós na tree e uma referência ao menor nó quando a contagem atinge 5.000. Quando a contagem atinge 5.000, cada novo número a ser incluído pode ser comparado a o menor item da tree. Se maior, o novo número pode ser adicionado então o menor removido e o novo menor calculado (que deve ser muito simples já tendo o menor anterior).

Minha preocupação com essa solução é que a tree binária naturalmente ficará distorcida (como estou excluindo apenas de um lado).

Existe uma maneira de resolver este problema que não cria uma tree terrivelmente distorcida?

Caso alguém queira, eu incluí pseudo-código para minha solução abaixo:

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

    A solução mais simples para isso é manter um mínimo de tamanho máximo de 5000.

    • Toda vez que um novo número chega – verifique se o heap é menor que 5000, se for – adicione-o.
    • Se não estiver – verifique se o mínimo é menor que o novo elemento e, se estiver, retire-o e insira o novo elemento.
    • Quando você terminar – você tem um monte contendo 5000 maiores elementos.

    Esta solução é a complexidade O(nlogk) , onde n é o número de elementos k é o número de elementos que você precisa (5000 no seu caso).

    Isso pode ser feito também em O(n) usando algoritmo de seleção – armazena todos os elementos, e então encontra o 5001º maior elemento, e retorna tudo maior que ele. Mas é mais difícil de implementar e para uma input de tamanho razoável – pode não ser melhor. Além disso, se o stream contiver duplicatas, mais processamento será necessário.

    Use uma fila de prioridade (mínima). Adicione cada item recebido à fila e, quando o tamanho atingir 5.000, remova o elemento mínimo (superior) toda vez que você adicionar um elemento de input. A fila conterá os 5.000 maiores elementos e quando a input parar, basta remover o conteúdo. Esse MinPQ também é chamado de heap, mas esse é um termo sobrecarregado. Inserções e exclusões levam cerca de log2 (N). Onde N atinge o máximo de 5.000, isso seria um pouco mais de 12 [log2 (4096) = 12] vezes o número de itens que você está processando.

    Uma excelente fonte de informação é Algorithms, (4ª edição) de Robert Sedgewick e Kevin Wayne. Existe um excelente MOOC no coursera.org que é baseado neste texto.