Colas de prioridad en Java

Question

java.util.PriorityQueue permite pasar un Comparator en tiempo de construcción. Al insertar elementos, se ordenan según la prioridad especificada por el comparador.

¿Qué sucede cuando la prioridad de un elemento cambia después de haber sido insertado? ¿Cuándo se reordenan los elementos PriorityQueue? ¿Es posible sondear un elemento que en realidad no tiene una prioridad mínima?

¿Hay buenas implementaciones de una cola de prioridad que permita actualizaciones de prioridad eficientes?

Answer 1

Debe quitar el elemento, cambiarlo y volver a insertar, ya que el pedido se produce cuando se inserta. Aunque implica varios pasos, es eficiente podría ser lo suficientemente bueno. (Me acabo de dar cuenta de que el comentario sobre la eliminación es O (n).)

Un problema es que también volverá a ordenar cuando elimine el elemento, que es redundante si va a volver a insertarlo un momento luego. Si implementa su propia cola de prioridad desde cero, podría tener una actualización() que omita este paso, pero la extensión de la clase de Java no funcionará porque todavía está limitado a eliminar() y agregar() proporcionado por la base.

Answer 2

Me esperar la PriorityQueue a no cambiar el orden de las cosas - y que podría ser muy confuso si se trata de hacer una búsqueda binaria para encontrar el lugar adecuado para poner las nuevas entradas.

En general, esperaría que cambiar la prioridad de algo que ya está en una cola sea una mala idea, al igual que cambiar los valores que componen una clave en una tabla hash.