Actualización de Java PriorityQueue cuando sus elementos cambian de prioridad
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 que el comparador calcula la prioridad) pueden cambiar después de la inserción inicial. La mayoría de las personas han sugerido la solución simple de eliminar el objeto, actualizar los valores y volver a insertarlo, ya que es cuando se pone en acción el comparador de la cola de prioridad.
¿Hay una mejor manera que simplemente crear una clase wrapper alrededor de la PriorityQueue para hacer esto?
5 answers
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 se retira de la cola. El inconveniente es que no puede cambiar la prioridad después de insertar el elemento. Un mapa de árbol 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 quieres para escribir un wrapper, puede mover el código de comparación de enqueue a dequeue. Ya no necesitará ordenar en 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. Dado que necesita agregar código de sincronización al actualizar las prioridades, también podría simplemente desqueue y enqueue (necesita la referencia a la cola en ambos caso).
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2009-12-09 02:47:03
No se si hay una implementación Java, pero si está cambiando mucho los valores de clave, puede usar un montón de Fibonnaci, que tiene O(1) costo amortizado para disminuir un valor de clave de una entrada en el montón, en lugar de O(log(n)) como en un montón ordinario.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2009-12-09 03:58:28
Depende mucho de si usted tiene control directo de cuando los valores cambian.
Si sabe cuándo cambian los valores, puede eliminar y volver a insertar (lo que de hecho es bastante caro, ya que la eliminación requiere un análisis lineal sobre el montón!). Además, puede usar una estructura UpdatableHeap (aunque no en stock java) para esta situación. Esencialmente, 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. Tercero, puedes buscar un montón de Fibonacci que haga lo mismo.
Dependiendo de su velocidad 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.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2012-12-24 00:18:47
Para activar reheapify prueba esto:
if(!priorityQueue.isEmpty()) {
priorityQueue.add(priorityQueue.remove());
}
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2018-04-01 15:54:14
Algo que he intentado y funciona hasta ahora, es mirar a escondidas para ver si la referencia al objeto que estás cambiando es la misma que la cabecera de la Priority, si lo es, entonces poll(), cambia y vuelve a insertar; de lo contrario, puedes cambiar sin polling porque cuando se sondea la cabecera, entonces el montón se amontona de todos modos.
INCONVENIENTE: Esto cambia la prioridad para los Objetos con la misma Prioridad.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2018-05-20 05:32:58