Aggiornamento di Java PriorityQueue quando i suoi elementi cambiano priorità

Sto cercando di utilizzare un PriorityQueue per ordinare oggetti usando un Comparator .

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

C’è un modo migliore oltre a creare una class wrapper attorno a PriorityQueue per fare ciò?

Devi rimuovere e reinserire, poiché la coda funziona inserendo 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 è ansible 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, è ansible spostare il codice di confronto da enqueue 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).

Non so se esiste un’implementazione Java, ma se si stanno modificando molto i valori chiave, è ansible utilizzare un heap di Fibonnaci, che ha un costo ammortizzato O (1) per ridurre un valore chiave di una voce nell’heap, piuttosto di O (log (n)) come in un cumulo ordinario.

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

Se sai quando i valori cambiano, puoi rimuovere e reinserire (che in effetti è piuttosto costoso, poiché la rimozione richiede una scansione lineare sull’heap!). Inoltre, è ansible 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, potrebbe funzionare anche una scansione lineare / quicksort / QuickSelect ogni volta. In particolare se hai 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.

Per triggersre reheapify prova questo:

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

Qualcosa che ho provato e funziona fino ad ora, fa capolino per vedere se il riferimento all’object che stai cambiando è lo stesso del capo di PriorityQueue, se lo è, allora sondaggi (), cambia e reinserisci ; altrimenti è ansible cambiare senza eseguire il polling, perché quando si esegue il polling della testa, l’heap viene comunque ingrandito.

Verso il basso: cambia la priorità per gli oggetti con la stessa priorità.