java - ¿Cuándo debo usar un TreeMap sobre un PriorityQueue y viceversa?

priority-queue

Question

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 uno sobre el otro, no solo para este ejemplo, sino para hablar en general?

Answer 1

Depende de cómo implementes tu cola de prioridad. Según el libro de Cormen de segunda edición, el resultado más rápido es con un montón de Fibonacci.

Answer 2

En términos generales, es menos trabajo rastrear solo el elemento mínimo, usando un montón.

Un árbol está más organizado y requiere más cálculos para mantener esa organización. Pero si necesita acceder a cualquier clave, y no solo al mínimo, un montón no será suficiente, y la sobrecarga adicional del árbol se justifica.

Answer 3

Hay 2 diferencias que me gustaría señalar (y esto puede ser más relevante para la Diferencia entre PriorityQueue y TreeSet en Java, ya que esa pregunta se considera una duplicación de esta pregunta).

(1) PriorityQueue puede tener duplicados donde, como TreeSet, NO puede tener dups. Entonces, en Treeset, si su comparador considera 2 elementos iguales, TreeSet mantendrá solo uno de esos 2 elementos y desechará el otro.

(2) El iterador TreeSet atraviesa la colección en un orden ordenado, mientras que el iterador PriorityQueue NO se desplaza en orden ordenado. Para PriorityQueue Si desea obtener los elementos 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.

Answer 4

La regla de oro al respecto es:

TreeMap mantiene todos los elementos ordenados. (Tan intuitivamente, lleva tiempo construirlo)

PriorityQueue solo cuarentena min o max. Es menos costoso pero menos poderoso.

Answer 5

Todo depende de lo que quieras lograr. Aquí están los puntos principales a considerar antes de elegir uno sobre el otro.

1. PriorityQueue permite duplicar (es decir, con la misma prioridad) mientras que TreeMap no lo hace.
2. La complejidad de PriorityQueue es O (n) (cuando aumenta su tamaño), mientras que TreeMap es O (logn) (ya que se basa en Red Black Tree)
3. PriorityQueue se basa en Array, mientras que en TreeMap los nodos están vinculados entre sí, por lo que el método de PriorityQueue tomaría O (n) tiempo mientras que TreeMap tomaría O (logn) tiempo.

Answer 6

Totalmente de acuerdo con Erickson en que la cola de prioridad solo le da el elemento mínimo / máximo.

Además, debido a que 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 más grandes en una matriz de N , la complejidad del tiempo sería O(N*LogM) y la complejidad del espacio sería O(M) . Pero si lo haces en un mapa, la complejidad del tiempo es O(N*logN) y el espacio es O(N) . Esto es bastante fundamental, mientras que debemos usar la cola de prioridad en algunos casos, por ejemplo, M es solo una constante como 10.

Answer 7

Una de las diferencias es que eliminar (Objeto) y contiene (Objeto) son lineales O (N) en un montón de prioridad basado en PriorityQueue (como Oracle), pero O (registro (N)) para un TreeSet / Map.

Por lo tanto, si tiene una gran cantidad de elementos y elimina muchos (Objeto) o contiene (Objeto), un TreeSet / Map puede ser más rápido.