Conservare il più grande 5000 numeri da un flusso di numeri

Question

Dato il seguente problema:

"Store più grandi 5000 numeri da un flusso di numeri"

La soluzione che viene in mente è una albero di ricerca binario che mantiene un conteggio del numero di nodi nell'albero e un riferimento al nodo più piccolo una volta che il conteggio raggiunge 5000. Quando il conteggio raggiunge 5000, ogni nuovo numero da aggiungere può essere confrontato con l'elemento più piccolo nell'albero. Se maggiore, è possibile aggiungere il nuovo numero, quindi il più piccolo rimosso e il nuovo più piccolo calcolato (che dovrebbe essere molto semplice avendo già il più piccolo precedente).

La mia preoccupazione per questa soluzione è che l'albero binario sarà naturalmente distorto (dato che sto cancellando solo da un lato).

C'è un modo per risolvere questo problema che non creerà un albero terribilmente distorto?

Nel caso qualcuno lo vuole, ho incluso pseudo-codice per la mia soluzione in modo molto più in basso:

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

Answer 1

La soluzione più semplice per questo è mantenere un minimo heap di dimensione massima 5000.

• Ogni volta che arriva un nuovo numero, verifica se l'heap è più piccolo di 5000, se lo è - aggiungilo.
• Se non lo è, verifica se il minimo è minore del nuovo elemento e, in caso affermativo, espellilo e inserisci invece il nuovo elemento.
• Al termine, si dispone di un heap contenente 5000 elementi più grandi.

Questa soluzione è O(nlogk) complessità, dove n è il numero di elementi e k è il numero di elementi necessari (5000 nel tuo caso).

Può essere eseguito anche in O(n) utilizzando selection algorithm - memorizza tutti gli elementi, quindi trova il 5001 ° elemento più grande e restituisce tutto più grande di esso. Ma è più difficile da implementare e per input di dimensioni ragionevoli - potrebbe non essere migliore. Inoltre, se lo stream contiene duplicati, è necessaria più elaborazione.

Answer 2

Utilizzare una coda di priorità (minima). Aggiungi ogni elemento in entrata alla coda e quando la dimensione raggiunge 5.000 rimuovi l'elemento minimo (superiore) ogni volta che aggiungi un elemento in entrata. La coda conterrà i 5000 elementi più grandi e quando l'input si interrompe, basta rimuovere il contenuto. Questo MinPQ è anche chiamato heap, ma è un termine sovraccarico. Inserzioni e cancellazioni prendono circa log2 (N). Dove N max a 5.000 questo sarebbe poco più di 12 [log2 (4096) = 12] volte il numero di elementi che stai elaborando.

Un'eccellente fonte di informazioni è Algorithms, (4th Edition) di Robert Sedgewick e Kevin Wayne. C'è un MOOC eccellente su coursera.org basato su questo testo.