Code prioritarie in Java

Question

java.util.PriorityQueue consente di passare uno Comparator in fase di costruzione. Quando si inseriscono elementi, vengono ordinati in base alla priorità specificata dal comparatore.

Cosa succede quando la priorità di un elemento cambia dopo che è stata inserita? Quando sono gli elementi di riordino PriorityQueue? È possibile eseguire il polling di un elemento che in realtà non ha priorità minima?

Esistono buone implementazioni di una coda di priorità che consentono aggiornamenti di priorità efficienti?

Answer 1

È necessario rimuovere l'elemento, modificarlo e reinserirlo, poiché l'ordine si verifica quando viene inserito. Anche se comporta diversi passaggi, è efficiente potrebbe essere abbastanza buono. (Ho appena notato che il commento sulla rimozione è O (n).)

Un problema è che verrà anche riordinato quando si rimuove l'elemento, che è ridondante se si sta per reinserirlo un momento dopo. Se implementi la tua coda di priorità da zero, potresti avere un update() che salta questo passaggio, ma l'estensione della classe di Java non funzionerà perché sei ancora limitato a remove() e add() fornito dalla base.

Answer 2

avrei aspetterebbe il PriorityQueue di non riordinare le cose - e si potrebbe ottenere molto confuso se si cerca di fare una ricerca binaria per trovare il posto giusto per mettere le nuove voci.

In generale, mi aspetto che cambiare la priorità di qualcosa già in coda sia una cattiva idea, proprio come cambiare i valori che costituiscono una chiave in una tabella hash.