Aggiornamento di Java PriorityQueue quando i suoi elementi cambiano priorità

Question

Sto tentando di utilizzare uno PriorityQueue per ordinare gli oggetti utilizzando un Comparator.

Questo può essere ottenuto facilmente, ma le variabili di classe degli oggetti (con cui il comparatore calcola la priorità) possono cambiare dopo l'inserimento iniziale. La maggior parte delle persone ha suggerito la semplice soluzione di rimuovere l'oggetto, aggiornando i valori e reinserendolo nuovamente, poiché questo è quando il comparatore della coda di priorità viene messo in azione.

C'è un modo migliore oltre alla semplice creazione di una classe wrapper attorno a PriorityQueue per fare ciò?

Answer 1

È necessario rimuovere e reinserire, poiché la coda funziona inserendo i nuovi elementi nella posizione appropriata quando vengono inseriti. Questo è molto più veloce dell'alternativa di trovare l'elemento con la priorità più alta ogni volta che si esce dalla coda. Lo svantaggio è che non è possibile modificare la priorità dopo che l'elemento è stato inserito. Una TreeMap ha la stessa limitazione (come una HashMap, che si interrompe anche quando il codice hash dei suoi elementi cambia dopo l'inserimento).

Se si desidera scrivere un wrapper, è possibile spostare il codice di confronto da accodamento a dequeue. Non avresti più bisogno di ordinare a tempo di attesa (perché l'ordine che crea non sarebbe comunque affidabile se permetti le modifiche).

Ma questo si comporta in modo peggiore e si desidera sincronizzarsi in coda se si cambiano le priorità. Poiché è necessario aggiungere il codice di sincronizzazione quando si aggiornano le priorità, si potrebbe anche solo deselezionare e accodare (è necessario il riferimento alla coda in entrambi i casi).

Answer 2

Non so se esiste un'implementazione Java, ma se si modificano valori chiave molto, è possibile utilizzare un heap di Fibonnaci, che ha un costo ammortizzato O (1) per diminuire un valore chiave di un entrata nell'heap, piuttosto che O (log (n)) come in un heap ordinario.

Answer 3

Dipende molto dal fatto che si abbia il controllo diretto di quando i valori cambiano.

Se si conosce quando i valori cambiano, è possibile rimuovere e reinserire (che in effetti è piuttosto costoso, in quanto la rimozione richiede una scansione lineare sull'heap!). Inoltre, è possibile utilizzare una struttura UpdatableHeap (non in stock java) per questa situazione. Essenzialmente, questo è un heap che tiene traccia della posizione degli elementi in una mappa di hash. In questo modo, quando la priorità di un elemento cambia, può riparare l'heap. Terzo, puoi cercare un heap di Fibonacci che faccia lo stesso.

A seconda della frequenza di aggiornamento, una scansione lineare/quicksort/QuickSelect ogni volta potrebbe funzionare anche. In particolare se si dispone di molti più aggiornamenti di pull s, questa è la strada da percorrere. QuickSelect è probabilmente il migliore se si dispone di batch di aggiornamento e quindi lotti di operazioni di pull.