Come posso tenere traccia in modo efficiente dell'elemento più piccolo in una raccolta?

Question

Nella vena di domande di programmazione:supponiamo che ci sia una raccolta di oggetti che possono essere confrontati tra loro e ordinati.Qual è il modo più efficiente per tenere traccia dell'elemento più piccolo nella raccolta man mano che gli oggetti vengono aggiunti e l'elemento più piccolo corrente viene occasionalmente rimosso?

Answer 1

Usare un heap minimo è il modo migliore.

http://en.wikipedia.org/wiki/Heap_(struttura_dati)

È fatto su misura per questa applicazione.

Answer 2

Se hai bisogno di inserimenti e rimozioni casuali, il modo migliore è probabilmente un array ordinato.Gli inserimenti e le rimozioni dovrebbero essere O(log(n)).

Answer 3

@Harpreet
Questo non è ottimale.Quando un oggetto viene rimosso, erickson dovrà scansionare l'intera collezione per trovare il nuovo più piccolo.

Vuoi documentarti Albero di ricerca binario'S.La SM ha una buona luogo per iniziare il cammino.Ma potresti voler prendere un libro come Introduzione agli algoritmi (Cormen, Leiserson, Rivest, Stein) se vuoi approfondire.

Answer 4

Per rimozioni occasionali a Mucchio di Fibonacci è ancora più veloce del min-heap.L'inserimento è O(1) e anche la ricerca del minimo è O(1).La rimozione è O(log(n))

Answer 5

Se hai bisogno di inserto e rimozione casuali, il modo migliore è probabilmente un array ordinato.Gli inserti e le rimozioni dovrebbero essere O (log (n)).

Sì, ma dovrai riordinare ogni inserimento e (forse) ogni eliminazione, che, come hai affermato, è O(log(n)).

Con la soluzione proposta da Harpreet:

• hai un passaggio O (n) all'inizio per trovare l'elemento più piccolo
• successivamente gli inserti sono O(1) (è necessario solo 1 confronto con l'elemento più piccolo già noto)
• le eliminazioni saranno O(n) perché dovrai trovare nuovamente l'elemento più piccolo (tieni presente che la notazione Big O è il caso peggiore).Puoi anche ottimizzare controllando per vedere se l'elemento da eliminare è il più piccolo (conosciuto) e, in caso contrario, non eseguire alcun ricontrollo per trovare l'elemento più piccolo.

Quindi dipende.Uno di questi algoritmi sarà migliore per un caso d'uso con numerosi inserimenti e poche eliminazioni, ma l'altro è nel complesso più coerente.Penso che utilizzerei per impostazione predefinita il meccanismo di Harpreet a meno che non sapessi che il numero più piccolo verrebbe rimosso spesso, perché ciò espone un punto debole in quell'algoritmo.

Answer 6

Harpreet:

gli inserti sarebbero lineari poiché è necessario spostare gli elementi per un inserto.

Ciò non dipende dall'implementazione della raccolta?Se si comportasse come una lista concatenata, gli inserti sarebbero O(1), mentre se fossero implementati come un array sarebbero lineari, come hai affermato.

Answer 7

Dipende da quali operazioni è necessario che il contenitore supporti.UN min-heap è la soluzione migliore se potrebbe essere necessario rimuovere l'elemento min in un dato momento, sebbene diverse operazioni non siano banali (tempo log(n) ammortizzato in alcuni casi).

Tuttavia, se hai solo bisogno di spingere/popare dalla parte anteriore/posteriore, puoi semplicemente utilizzare un mindeque che raggiunge un tempo costante ammortizzato per tutte le operazioni (incluso findmin).Tu puoi fare una ricerca su Scholar.google.com per saperne di più su questa struttura.Un amico e io abbiamo recentemente collaborato per raggiungere una versione di mindeque molto più facile da comprendere e da implementare.Se questo è quello che stai cercando, potrei postare i dettagli per te.