Reheapify java.util.PriorityQueue después de actualizar los elementos

Question

Tengo una PriorityQueue que contiene referencias a algunos objetos. Cuando inicialmente inserto los elementos en la cola de prioridad, el ordenamiento es mantenido por la estructura de datos. Ahora, después de una operación de eliminación, actualizo algunas de las referencias que están siendo retenidas por la cola de prioridad. Idealmente, esto requiere una operación de reheapify en la cola de prioridad, pero como es obvio, ya que estoy modificando las referencias seleccionadas externamente, no se puede desencadenar una reheapify. Entonces, ¿cuál es la mejor manera de asegurar que puedo obtener la ventaja de un montón como máximo de extracción rápida en presencia de modificaciones a elementos arbitrarios dentro de la cola? Veo que necesito una mejor estructura de datos?

Para ser más específico, necesito una implementación de algo así como un montón de Fibonacci en Java. http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm ¿Está eso disponible?

Answer 1

Puede usar su propio árbol que permita elementos duplicados en lugar de montón. Más fácil, puede usar TreeMap<PriorityKey, LinkedHashSet<Value>>. Todas las operaciones son O (log priorityType):

• adición es get(priority).add(value), si obtener retornos nula, put(priority, new LinkedHashSet())
• la eliminación de un elemento arbitrario es similar, excepto necesidades para eliminar la prioridad del mapa si el conjunto es vacío.
• poll() es

-

Entry<PriorityKey, LinkedHashSet<Value>> e = map.firstEntry(); 
if (e==null) return null; 
Iterator<Value> i = e.getValue().iterator(); 
Value v = i.next(); //must always have at least one element. 
i.remove(); 
if (!i.hasNext()) map.remove(e.getKey()); 
return v; 

Aún si tiene que cambiar la prioridad tiene que quitar y añadir el elemento.

Answer 2

Tal vez un NavigableMap se adapte a sus necesidades: fácil identificación del elemento "más alto" o "más bajo", inserción rápida y tiempo de acceso, y puede actualizar los valores fácilmente.

http://docs.oracle.com/javase/7/docs/api/java/util/NavigableMap.html

TreeMap implementa NavigableMap, y por lo tanto proporciona los/lastEntry métodos firstEntry, y muchos más.