Coda a priorità Java

Ogni tanto dobbiamo elaborare gli elementi di una coda in un ordine particolare. La coda prioritaria è una struttura dati che svolge questo compito. La coda prioritaria di Java è diversa dalla “normale” coda. Invece del principio “First-In-First-Out”, recupera gli elementi in base alla loro priorità.

Coda Prioritaria Java

La classe java.util.PriorityQueue ci fornisce un’implementazione di questo tipo di dato, utilizzando internamente un’implementazione a heap di priorità. La coda prioritaria di Java è una coda illimitata. È stata introdotta in Java 1.5 e migliorata nel rilascio di Java SE 8. La coda prioritaria è implementata internamente seguendo la struttura dati “Priority Heap”. Ecco la gerarchia della classe PriorityQueue: Diagramma di Classe della Coda Prioritaria:

Costruttori della Coda Prioritaria Java

1. PriorityQueue() – Crea una coda prioritaria con la capacità iniziale predefinita, ovvero 11
2. PriorityQueue(Collection c) – Crea una coda prioritaria con gli elementi nella collezione specificata
3. CodaPriorita(int capacitaIniziale) – Crea una CodaPriorita con la capacità iniziale specificata
4. CodaPriorita(int capacitaIniziale, Comparatore comparatore) – Crea una CodaPriorita con la capacità iniziale fornita e l’ordinamento degli elementi è secondo il comparatore specificato
5. CodaPriorita(CodaPriorita c) – Crea una CodaPriorita contenente gli elementi nella coda prioritaria specificata
6. CodaPriorita(InsiemeOrdinato c) – Crea una CodaPriorita contenente gli elementi nell’insieme ordinato specificato

Gli elementi della coda prioritaria sono ordinati secondo il loro ordinamento naturale a meno che non forniamo un Comparatore durante la creazione. Gli elementi sono ordinati in ordine ascendente per impostazione predefinita, quindi la testa della coda è l’elemento il cui livello di priorità è più basso. Se ci sono due elementi che sono idonei a diventare la testa contemporaneamente, questo tipo di legami viene risolto arbitrariamente.

Esempio di CodaPriorita in Java

Creiamo una CodaPriorita, contenente varie attività:

PriorityQueue tasks=new PriorityQueue();
tasks.add("task1");
tasks.add("task4");
tasks.add("task3");
tasks.add("task2");
tasks.add("task5");

Questo crea una CodaPriorita di attività, che verranno ordinate secondo l’ordinamento naturale delle Stringhe. Creiamo un’altra CodaPriorita che ordina le attività nell’ordine inverso dell’ordinamento naturale. Quindi dobbiamo passare un Comparatore:

PriorityQueue reverseTasks=new PriorityQueue(Comparator.reverseOrder());
reverseTasks.add("task1");
reverseTasks.add("task4");
reverseTasks.add("task3");
reverseTasks.add("task2");
reverseTasks.add("task5");

Metodi di PriorityQueue di Java

Adesso, diamo un’occhiata a tutti i metodi disponibili per PriorityQueue e li utilizziamo:

1. Boolean add(E e) – Questo metodo inserisce l’elemento specificato nella coda. Abbiamo già aggiunto 5 compiti nella nostra coda usando questo metodo.

2. Comparator comparator() – Questo metodo restituisce il Comparator usato per ordinare gli elementi in questa coda. Restituisce null se non è stato specificato alcun comparatore e la coda è ordinata secondo l’ordinamento naturale dei suoi elementi. Quindi, se facciamo:

   System.out.println(tasks.comparator());
   System.out.println(reverseTasks.comparator());
   

   Il risultato sarà:

   null
   java.util.Collections$ReverseComparator@15db9742
   

3. boolean contains(Object o) – Restituisce true se la coda contiene l’elemento specificato. Verifichiamo se “task3” appartiene alla coda prioritaria tasks:

   System.out.println(tasks.contains("task3"));
   

   Questo stampa:

   true
   

4. boolean offer(E e) – Proprio come il metodo add(), questo metodo aggiunge anche un elemento alla coda. I metodi offer() e add() sono effettivamente leggermente diversi per code con capacità limitata, ma nel caso di PriorityQueue, sono uguali. A differenza di add(), offer() non genera un’eccezione anche se non riesce ad aggiungere l’elemento alla coda.

5. E peek() – Recupera la testa di questa coda o restituisce null se questa coda è vuota. In altre parole, restituisce l’elemento con la priorità più alta. Quindi il codice seguente:

   System.out.println(tasks.peek());
   System.out.println(reverseTasks.peek());
   

   Ci restituisce:

   task1
   task5
   

6. Il metodo poll() – Questo metodo recupera anche la testa della coda (elemento con la priorità più alta), o restituisce null se la coda è vuota. Ma a differenza di peek(), rimuove anche l’elemento. Quindi, se chiamiamo poll():

   System.out.println("Poll su tasks: "+tasks.poll());
   System.out.println("Poll su reverseTasks: "+reverseTasks.poll());
   

   E poi peek:

   System.out.println("Peek su tasks: "+tasks.peek());
   System.out.println("Peek su reverseTasks: "+reverseTasks.peek());
   

   Avremo il seguente output:

   Poll su tasks: task1
   Poll su reverseTasks: task5
   Peek su tasks: task2
   Peek su reverseTasks: task4
   

7. int size() – Restituisce il numero di elementi nella coda.

8. boolean remove(Object o) – Rimuove l’elemento specificato dalla coda, se presente. Se due elementi uguali sono presenti, ne rimuove solo uno.

9. Object[] toArray() – Restituisce un array contenente tutti gli elementi nella coda.

10. T[] toArray(T[] a) – Restituisce un array contenente tutti gli elementi nella coda, e il tipo dell’array restituito è quello dell’array specificato.

11. Iterator iterator() – Restituisce un iteratore per la coda.

12. void clear() – Rimuove tutti gli elementi dalla coda.

A parte questi, la PriorityQueue eredita anche i metodi dalle classi Collection e Object.

Complessità temporale di PriorityQueue di Java

1. Per i metodi di inserimento e rimozione, la complessità temporale è O(log(n))
2. Per i metodi remove(Object) e contains(Object), la complessità temporale è lineare
3. Per i metodi di recupero, ha una complessità temporale costante

Questa implementazione della coda a priorità non è thread-safe. Quindi, se abbiamo bisogno di accesso sincronizzato, dobbiamo usare PriorityBlockingQueue. Riferimento: API Doc