Coda di priorità Java

Question

Java coda di priorità è una struttura di dati con O (log n) complessità per put (inserimento) e O (log n) per sondaggio (recupero e rimozione dell'elemento min).

La multimap di C ++ STL ha la stessa funzionalità ma O ( 1) complessità per il recupero e la rimozione dell'elemento minimo (inizio e cancellazione). Esiste un equivalente in Java?

Answer 1

Collezioni Google fornisce un'implementazione multimap. In particolare, una TreeMultimap può utilizzare i comparatori per ordinare in base a chiavi, valori o entrambi.

Answer 2

Prova le Collezioni Apache Commons .

MultiHashMap e MultiValueMap (collegati da quella pagina) implementano effettivamente l'interfaccia.

In realtà esiste una Coda di priorità anche lì, ma è ammortizzato a favore di pacchetto buffer .

Answer 3

Innanzitutto, verificherei che la multimappa di C ++ fornisca effettivamente O (1) per rimuovere l'elemento min. Le strutture più comuni per le mappe / code prioritarie ordinate sono strutture ad albero in cui interrogazione l'elemento min ha complessità O (1), ma rimuovendo è O (log n).

Detto questo, penso che un skip list (come implementato dalla ConcurrentSkipListMap ) potrebbe darti O (1) per la rimozione dell'elemento minimo, ma io ' non ne sono assolutamente sicuro. Uno dei problemi nella valutazione delle prestazioni di ConcurrentSkipListMap è che le operazioni di attraversamento "riordinano". marcatori lasciati da precedenti eliminazioni. Quindi la complessità di un'operazione può effettivamente dipendere da quali erano le operazioni precedenti. (D'altra parte, a un certo livello, è vero praticamente per qualsiasi algoritmo: se alcuni dati si trovano nella cache della CPU può dipendere dal fatto che un'operazione precedente li abbia messi lì ...)

P.S. Hai dimenticato di dire: guarda ConcurrentSkipListMap.pollFirstEntry () .

Answer 4

std: multimap sarà una struttura ad albero, il che significa che aggiungere e rimuovere insieme sarà O (log n).