Parece que ambos te permiten recuperar el mínimo, que es lo que necesito para el algoritmo de Prim, y me obligan a eliminar y volver a insertar una clave para actualizar su valor. ¿Hay alguna ventaja de usar una sobre la otra, no solo para este ejemplo, sino en términos generales?¿Cuándo debería usar un TreeMap sobre PriorityQueue y viceversa?
En términos generales, es menos trabajo rastrear solo el elemento mínimo, utilizando un montón.
Un árbol está más organizado, y requiere más computación para mantener esa organización. Pero si necesita acceder a cualquier clave, y no solo el mínimo, un montón no será suficiente y la sobrecarga adicional del árbol está justificada.
"es menos trabajo rastrear solo el elemento mínimo, usando un montón" - Más específicamente, un PriorityQueue le permite * mirar * al elemento principal en ** tiempo ** constante. Un TreeMap requiere O (logn) para mirar. Ambos requieren O (logn) en cualquier momento que realmente separe ese elemento. – JMess
Depende de cómo implemente su Priority Queue. Según el segundo libro de Cormen, el resultado más rápido es con un montón de Fibonacci.
Una de las diferencias es que remove (Object) y contains (Object) son O lineales (N) en un PriorityQueue basado en heap normal (como Oracle), pero O (log (N)) para un TreeSet/Map.
Así que si tiene una gran cantidad de elementos y elimina mucho (Objeto) o contiene (Objeto), un TreeSet/Map puede ser más rápido.
Totalmente de acuerdo con Erickson en que la cola de prioridad solo le da el elemento mínimo/máximo.
Además, como la cola de prioridad es menos poderosa para mantener el orden total de los datos, tiene la ventaja en algunos casos especiales. Si desea rastrear los elementos más grandes M en una matriz de N, la complejidad de tiempo sería O(N*LogM) y la complejidad del espacio sería O(M). Pero si lo haces en un mapa, la complejidad de tiempo es O(N*logN) y el espacio es O(N). Esto es absolutamente fundamental, mientras que hay que utilizar cola de prioridad en algunos casos, por ejemplo M es simplemente una constante como 10.
buena nota, pero podrías imitar este comportamiento para el espacio 'O (m)' con un TreeMap también. Simplemente elimine manualmente los elementos más grandes después de alcanzar un determinado tamaño. – A1m
La regla de oro de ello es:
TreeMap mantiene todos los elementos ordenada. (Así que intuitivamente, lleva tiempo construirlo)
PrioridadQueue solo cuarentena mín. O máx. Es menos costoso pero menos poderoso.
Hay 2 diferencias que me gustaría señalar (y esto puede ser más relevante para Difference between PriorityQueue and TreeSet in Java? ya que esa pregunta se considera un duplicado de esta pregunta).
(1) PriorityQueue puede tener duplicados donde TreeSet NO puede tener dups. Entonces, en Treeet, si su comparador considera que 2 elementos son iguales, TreeSet conservará solo uno de esos 2 elementos y desechará el otro.
(2) TreeSet iterator atraviesa la colección en un orden ordenado, mientras que el iterador PriorityQueue NO atraviesa en orden ordenado. Para PriorityQueue Si desea obtener los artículos en orden, debe destruir la cola llamando a remove() repetidamente.
Supongo que la discusión se limita a la implementación de Java de estas estructuras de datos.
¿Hay una estructura de datos estándar que proporcione el tiempo de registro (N) para eliminar como TreeSet pero también permite elementos iguales (desde el método 'igual' prospectivo)? – beemaster
Todo depende de lo que desee lograr. Aquí están los puntos principales a considerar antes de elegir uno sobre otro.
interesante, la única respuesta que señala una gran desventaja de O para TreeMap. ¿Tiene una fuente para la complejidad del espacio de un TreeMap? – A1m
Tenga en cuenta que un 'TreeMap' no ** requiere ** que elimine y vuelva a insertar una clave para actualizar su valor. Una llamada 'put (key, value)' actualizará el valor de una tecla si (o un valor clave "igual") ya está en el mapa. –
hmm, eso significa que no puedo tener valores con la misma clave, mientras que en una cola de prioridad creo que puedo. – iceburn
Puede usar un comparador personalizado para resolver esto y ajustar su clave en un objeto (tal vez resolver vínculos por identificación de borde, por ejemplo). –