Java fila de prioridade

Question

O Java prioridade da fila é uma estrutura de dados com complexidade O(log n) para colocar (inserção) e O(log n) para sondagem (a recuperação e remoção do elemento min).

C ++ STL do multimap tem a mesma funcionalidade, mas a complexidade O(1) para recuperação e remoção do elemento min (início e de apagamento). Existe um equivalente em Java?

Answer 1

Google Collections fornece uma implementação Multimap. Especificamente, um TreeMultimap pode usar comparadores para classificar quer com base em chaves, valores ou ambos.

Answer 2

Tente o Apache Commons Collections .

MultiHashMap e MultiValueMap (ligada a partir dessa página) realmente implementar a interface.

Na verdade, há um Priority Queue lá também, mas é depreciado em favor do tampão pacote .

Answer 3

Primeiro, gostaria de verificar que C ++ 's multimap realmente dá o (1) para remover o elemento min. As estruturas mais comuns para os mapas sotred / filas de prioridade são estruturas de árvore em que consulta o elemento min tem ó (1) a complexidade, mas remover que é O (N log N).

Dito isso, eu acho que uma lista de ignorar (como implementado pelo Java do ConcurrentSkipListMap ) pode dar-lhe O (1) para a remoção do elemento mínimo, mas eu' m não absolutamente certo. Um dos problemas na avaliação do desempenho de ConcurrentSkipListMap é que as operações de passagem "arrumar" marcadores deixados por eliminações anteriores. Assim, a complexidade de uma operação pode realmente depender do que as operações anteriores foram. (Por outro lado, em algum nível, isso é verdade de praticamente qualquer algoritmo: se alguns dados está na CPU cache pode depender se uma operação anterior colocá-lo lá ...)

P.S. Esqueci de dizer:. Olhada ConcurrentSkipListMap.pollFirstEntry ()

Answer 4

std:multimap será uma estrutura de árvore, o que significa que adicionar e remover juntos será O (log n).