Actualización de Java PriorityQueue cuando sus elementos cambian de prioridad

priority queue java 8

Question

Estoy tratando de usar un PriorityQueue para ordenar objetos usando un Comparator .

Esto se puede lograr fácilmente, pero las variables de clase de objetos (con las cuales el comparador calcula la prioridad) pueden cambiar después de la inserción inicial. La mayoría de la gente ha sugerido la solución simple de eliminar el objeto, actualizar los valores y reinsertarlo de nuevo, ya que es cuando se pone en acción el comparador de la cola de prioridad.

¿Hay alguna otra manera mejor que simplemente crear una clase contenedora alrededor de PriorityQueue para hacer esto?

Answer 1

Algo que probé y funciona hasta ahora, es ver si la referencia al objeto que estás cambiando es la misma que la cabecera de PriorityQueue, si es así, entonces sondeas (), cambias y luego vuelves a insertar ; de lo contrario, puede cambiar sin sondear porque cuando se sondea la cabeza, el montón queda heapificado de todos modos.

ATRÁS: Esto cambia la prioridad para Objetos con la misma Prioridad.

Answer 2

Debe eliminar y volver a insertar, ya que la cola funciona colocando nuevos elementos en la posición adecuada cuando se insertan. Esto es mucho más rápido que la alternativa de encontrar el elemento de mayor prioridad cada vez que salga de la cola. El inconveniente es que no puede cambiar la prioridad después de que se haya insertado el elemento. Un TreeMap tiene la misma limitación (al igual que un HashMap, que también se rompe cuando el hashcode de sus elementos cambia después de la inserción).

Si desea escribir un contenedor, puede mover el código de comparación de enqueue para quitar la cola. Ya no necesitaría ordenar el tiempo de enqueue (porque el orden que crea no sería confiable de todos modos si permite cambios).

Pero esto funcionará peor, y desea sincronizar en la cola si cambia alguna de las prioridades. Como necesita agregar un código de sincronización cuando actualiza las prioridades, también puede dequeuear y poner en cola (necesita la referencia a la cola en ambos casos).

Answer 3

Depende mucho de si tiene control directo de cuándo cambian los valores.

Si sabe cuándo cambian los valores, puede eliminar y volver a insertar (que de hecho es bastante caro, ya que la eliminación requiere un escaneo lineal sobre el montón). Además, puede usar una estructura de UpdatableHeap (no en stock java) para esta situación. Esencialmente, ese es un montón que rastrea la posición de los elementos en un hashmap. De esta manera, cuando la prioridad de un elemento cambia, puede reparar el montón. En tercer lugar, puede buscar un montón de Fibonacci que haga lo mismo.

Dependiendo de su tasa de actualización, un escaneo lineal / quicksort / QuickSelect cada vez también podría funcionar. En particular, si tiene muchas más actualizaciones que pull s, este es el camino a seguir. QuickSelect es probablemente mejor si tiene lotes de actualización y luego lotes de operaciones de extracción.

Answer 4

No sé si hay una implementación de Java, pero si está cambiando mucho los valores clave, puede usar un montón Fibonnaci, que tiene O (1) costo amortizado para disminuir el valor clave de una entrada en el montón, en lugar de que O (log (n)) como en un montón ordinario.

Answer 5

Para activar Reheapify prueba esto:

if(!priorityQueue.isEmpty()) { priorityQueue.add(priorityQueue.remove()); }