Cola de prioridad de Java

Question

Java cola prioritaria es una estructura de datos con complejidad O (log n) para put (inserción) y O (log n) para sondeo (recuperación y eliminación del elemento min).

C ++ STL's multimap tiene la misma funcionalidad pero O ( 1) complejidad para la recuperación y eliminación del elemento min (comenzar y borrar). ¿Hay un equivalente en Java?

Answer 1

Google Collections proporciona una implementación de mapa múltiple. Específicamente, un TreeMultimap puede usar comparadores para ordenar según claves, valores o ambos.

Answer 2

Pruebe el Apache Commons Collections .

MultiHashMap y MultiValueMap (vinculados desde esa página) realmente implementan la interfaz.

En realidad, hay una Priority Queue allí también, pero se deprecia a favor de paquete de almacenamiento intermedio .

Answer 3

Primero, comprobaría que el multimapa de C ++ realmente le da a O (1) para eliminar el elemento min. Las estructuras más comunes para los mapas de puntos / colas de prioridad son las estructuras de árbol en las que consultar el elemento min tiene O (1) complejidad, pero eliminar es O (log n).

Dicho esto, creo que una lista de omisión (implementada por ConcurrentSkipListMap de Java ) podría darle O (1) para eliminar el elemento mínimo, pero yo ' No estoy absolutamente seguro. Uno de los problemas al evaluar el rendimiento de ConcurrentSkipListMap es que las operaciones transversales '' arreglan '' marcadores dejados por eliminaciones anteriores. Por lo tanto, la complejidad de una operación puede depender de cuáles fueron las operaciones anteriores. (Por otro lado, en cierto nivel, eso es cierto para casi cualquier algoritmo: si algunos datos están en el caché de la CPU puede depender de si una operación anterior lo puso allí ...)

P.S. Olvidé decir: mira ConcurrentSkipListMap.pollFirstEntry () .

Answer 4

std: multimap será una estructura de árbol, lo que significa que agregar y eliminar juntos será O (log n).