Reheapify java.util.PriorityQueue dopo l'aggiornamento degli elementi

Question

Ho un PriorityQueue contenente riferimenti ad alcuni oggetti. Quando inizialmente inserisco gli elementi nella coda di priorità, l'ordine viene mantenuto dalla struttura dei dati. Ora dopo un'operazione di rimozione aggiorno alcuni dei riferimenti che sono trattenuti dalla coda di priorità. Idealmente ciò richiede un'operazione di reheapify sulla coda di priorità, ma come è ovvio visto che sto modificando i riferimenti selezionati esternamente, non è possibile attivare una reheapify. Quindi qual è il modo migliore per assicurarmi di essere in grado di trarre il massimo vantaggio da un heap come fast extract max in presenza di modifiche a elementi arbitrari all'interno della coda? Vedo che ho bisogno di una struttura dati migliore?

Per essere più specifici ho bisogno di un'implementazione di qualcosa come un heap di Fibonacci in Java. http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm È disponibile?

Answer 1

È possibile utilizzare il proprio albero che consente elementi duplicati anziché heap. Più facile però, è possibile utilizzare TreeMap<PriorityKey, LinkedHashSet<Value>>. Tutte le operazioni sono O (log priorityType):

• aggiunta è get(priority).add(value), se ottenere rendimenti nulli, put(priority, new LinkedHashSet())
• rimozione di un elemento arbitrario è simile, tranne che deve eliminare la priorità fuori dalla mappa se il set è vuoto.
• poll() è

-

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; 

Ancora se è necessario modificare la priorità è necessario rimuovere e aggiungere l'elemento.

Answer 2

Forse una NavigableMap si adatta alle tue esigenze: facile identificazione dell'elemento "più alto" o "più basso", inserimento veloce e tempo di accesso, e puoi aggiornare facilmente i valori.

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

TreeMap implementa NavigableMap, e quindi fornisce i/lastEntry metodi firstEntry, e molti altri.