Coda prioritaria Java: non una coda classica

In questo articolo impariamo una coda di priorità, classe Java, che implementa l'interfaccia Queue. Cosa sa un programmatore della normale Queue Interface? Prima di tutto, questa interfaccia si basa sul principio FIFO o "first in first out". Che ricorda una normale coda nel suo significato comune. Vuoi prendere un caffè da McDrive? Se la tua macchina è la prima vicino al finestrino, prenderai il caffè prima dell'autista che è dopo.

Dichiarazione dell'interfaccia di coda

public interface Queue<E> extends Collection<E>

Che cos'è una coda prioritaria

Che cos'è una coda prioritaria? Prima di tutto è una classe che implementa l'interfaccia Queue in caso di inserimento di un elemento dal retro e rimozione di un elemento dalla testa. Tuttavia non è una solita coda all'interno. L'ordine degli elementi della coda di priorità Java dipende dalla priorità degli elementi. L'elemento con la priorità più alta verrà spostato in testa alla coda. Se elimini (servi) l'elemento con il punteggio più alto, il secondo va in testa a prendere il suo caffè. Come viene determinata la priorità? Secondo la documentazione, gli elementi della coda prioritaria sono ordinati in base al loro ordinamento naturale o da un Comparatore fornito al momento della costruzione della coda, a seconda del costruttore utilizzato. Una coda di priorità basata su un heap minimo di priorità. Ciò significa che, in caso di elementi della coda di numeri, il primo elemento della coda sarà il minimo di questi numeri. Abbastanza spesso, dopo aver letto questa definizione, gli studenti principianti iniziano a pensare che la coda prioritaria sia ordinata in senso lineare. Cioè, se, diciamo, usiamo una coda i cui elementi sono numeri naturali, il primo elemento sarà il più piccolo e l'ultimo il più grande. Questo non è del tutto vero. Per capire come funziona effettivamente la coda di priorità e cosa offre, è necessario capire come funziona l'heap. Consideriamo la struttura interna della coda prioritaria usando un esempio un po' più tardi. Ora soffermiamoci sui suoi attributi esterni. quindi il primo elemento sarà il più piccolo e l'ultimo il più grande. Questo non è del tutto vero. Per capire come funziona effettivamente la coda di priorità e cosa offre, è necessario capire come funziona l'heap. Consideriamo la struttura interna della coda prioritaria usando un esempio un po' più tardi. Ora soffermiamoci sui suoi attributi esterni. quindi il primo elemento sarà il più piccolo e l'ultimo il più grande. Questo non è del tutto vero. Per capire come funziona effettivamente la coda di priorità e cosa offre, è necessario capire come funziona l'heap. Consideriamo la struttura interna della coda prioritaria usando un esempio un po' più tardi. Ora soffermiamoci sui suoi attributi esterni.

Costruttori e dichiarazione della classe PriorityQueue

La classe PriorityQueue fornisce 6 modi diversi per costruire una coda di priorità in Java.

• PriorityQueue() - coda vuota con la capacità iniziale predefinita (11) che ordina i suoi elementi in base al loro ordinamento naturale.
• PriorityQueue(Collection c) - coda vuota contenente gli elementi nella raccolta specificata.
• PriorityQueue(int initialCapacity) - coda vuota con la capacità iniziale specificata che ordina i suoi elementi in base al loro ordinamento naturale.
• PriorityQueue(int initialCapacity, Comparator comparator) - coda vuota con la capacità iniziale specificata che ordina i propri elementi in base al comparatore specificato.
• PriorityQueue(PriorityQueue c) - coda vuota contenente gli elementi nella coda di priorità specificata.
• PriorityQueue(SortedSet c) - coda vuota contenente gli elementi nel set ordinato specificato.

La coda prioritaria in Java viene dichiarata nel modo seguente:

public class PriorityQueue<E> extends AbstractQueue<E> implements Serializable

Creazione di PriorityQueue

Creiamo una coda prioritaria di numeri interi. Implementazione della coda prioritaria, codice Java:

PriorityQueue<Integer> numbers = new PriorityQueue<>();

Abbiamo creato una coda di priorità senza argomenti. In questo caso, la testa della coda prioritaria è il numero minimo della coda. Se rimuovi la testa, l'elemento successivo più piccolo prenderà questo posto. Quindi puoi rimuovere gli elementi dalla coda in ordine crescente. Se necessario è possibile modificare il principio di ordinamento utilizzando l'interfaccia Comparator.

Metodi Java PriorityQueue

La classe Java PriorityQueue ha metodi importanti per aggiungere, rimuovere e controllare elementi.

Inserisci gli elementi nella coda prioritaria

• boolean add(object) inserisce l'elemento specificato nella coda di priorità. Restituisce true in caso di successo. Se la coda è piena, il metodo genera un'eccezione.
• boolean offer(object) inserisce l'elemento specificato in questa coda di priorità. Se la coda è piena, il metodo restituisce false.

Puoi utilizzare entrambe le operazioni di addizione, non ci sono differenze per i casi di maggioranza. Ecco un piccolo esempio di iniziazione e aggiunta di elementi nella coda di priorità.

import java.util.PriorityQueue;
import java.util.Queue;
public class Priority2 {
    public static void main(String[] args) {
        Queue<Integer> priorityQueue1 = new PriorityQueue<>();
        for (int i = 5; i > 0; i--) {
            priorityQueue1.add(i);
        }
        System.out.println(priorityQueue1);
    priorityQueue1.offer(0);
        System.out.println(priorityQueue1);
    }
}

L'uscita è:

[1, 2, 4, 5, 3]
[0, 2, 1, 5, 3, 4]

L'ordine degli elementi sembra essere strano, lo spiegheremo più avanti.

Recupero e rimozione di elementi dalla coda prioritaria

• boolean remove(object) rimuove una singola istanza dell'elemento specificato da questa coda, se presente.
• L'oggetto poll() recupera e rimuove l'intestazione di questa coda. Restituisce null se la coda è vuota.
• void clear() rimuove tutti gli elementi dalla coda di priorità.
• Object element() recupera l'intestazione di questa coda senza rimuoverla. Genera NoSuchElementException se la coda è vuota.
• Object peek() recupera l'inizio della coda senza rimuoverlo. Restituisce null se la coda è vuota.

import java.util.PriorityQueue;
import java.util.Queue;
 
public class Priority2 {
    public static void main(String[] args) {
        Queue<Integer> priorityQueue = new PriorityQueue<>();
        //put 5 elements to the queue using add
        for (int i = 5; i > 0; i--) {
            priorityQueue.add(i);
        }
        System.out.println("the head of the queue = " + priorityQueue.peek());
        //removing element by element from the queue using poll and print it out
        while (!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.poll());
        }
        //put 5 new elements into the empty queue using offer
        for (int i = 10; i > 5; i--) {
            priorityQueue.offer(i);
        }
        System.out.println("now the head of the queue = " + priorityQueue.peek());
        System.out.println("the queue before removing 9:");
        System.out.println(priorityQueue);
        priorityQueue.remove(9);
        System.out.println("the queue after removing 9:");
        System.out.println(priorityQueue);
        //removing all the elements from the queue
        priorityQueue.clear();
        System.out.println(priorityQueue);
        //trying to print out the head of the empty Queue using peek - we'll get null
        System.out.println(priorityQueue.peek());
        //trying to print out the head of the empty Queue using element - we'll get the exception
        System.out.println(priorityQueue.element());
    }
}

Il risultato:

the head of the queue = 1
1
2
3
4
5
now the head of the queue = 6
the queue before removing 9:
[6, 7, 9, 10, 8]
the queue after removing 9:
[6, 7, 8, 10]
[]
null
Exception in thread "main" java.util.NoSuchElementException
  at java.base/java.util.AbstractQueue.element(AbstractQueue.java:136)
  at Priority2.main(Priority2.java:32)

Come puoi vedere, provare a stampare la testa della coda vuota usando il metodo element() porta a NoSuchElementexception .

Comparatore PriorityQueue

• Comparator comparator() restituisce il comparatore utilizzato per ordinare gli elementi nella coda. Restituisce null se la coda è ordinata secondo l'ordine naturale dei suoi elementi.

Coda di priorità Java, esempio con comparatore

Abbiamo usato l'ordine naturale (ascendente) negli esempi di codice sopra, ma a volte dovremmo cambiarlo. Ecco un esempio di coda di priorità Java, in cui creiamo la nostra classe comparatore interna che implementa l'interfaccia Comparator. Il nostro comparatore ordinerà gli elementi dal più grande al più piccolo.

import java.util.PriorityQueue;
import java.util.Comparator;
 
class Priority3 {
    public static void main(String[] args) {
        // Creating a priority queue with myComparator
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new MyComparator());
        for (int i = 5; i > 0; i--) {
            priorityQueue.add(i);
        }
        System.out.println("the head of Queue = " + priorityQueue.peek());
        while (!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.poll());
        }
    }
}
 
class MyComparator implements Comparator<Integer> {
    @Override
    public int compare(Integer number1, Integer number2) {
        int value = number1.compareTo(number2);
        //sorting elements from maximal to minimal
        if (value > 0) {
            return -1;
        } else if (value < 0) {
            return 1;
        } else {
            return 0;
        }
    }
}

Il risultato:

the head of Queue = 5
5
4
3
2
1

L'intestazione di Queue ora non è l'elemento minimo, ma massimo e l'ordine è stato modificato in invertito.

Iterazione su PriorityQueue tramite iteratore

ProrityQueue fa parte del framework Collection e implementa l' interfaccia Iterable<> . Per iterare sugli elementi di una coda di priorità è possibile utilizzare il metodo iterator() . Ecco un esempio:

import java.util.PriorityQueue;
import java.util.Iterator;
import java.util.Queue;
 
class Priority4 {
   public static void main(String[] args) {
       // Creating a priority queue
       Queue<Integer> priorityQueue = new PriorityQueue<>();
       //put 5 elements to the queue using add
       for (int i = 5; i > 0; i--) {
           priorityQueue.add(i);
       }
       //Iterating via iterator() method
       Iterator<Integer> iterator = priorityQueue.iterator();
       while (iterate.hasNext()) {
           System.out.print(iterator.next() + " ");
       }
   }
}

Il risultato:

1 2 4 5 3 

Altri metodi PriorityQueue

• boolean contains(Object o) restituisce true se la coda contiene l'elemento o.
• int size() restituisce il numero di elementi in questa coda.
• Object[] toArray() restituisce un array contenente tutti gli elementi in questa coda.

Ecco un esempio:

import java.util.PriorityQueue;
import java.util.Queue;
 
public class Priority5 {
   public static void main(String[] args) {
       Queue<Integer> priorityQueue = new PriorityQueue<>();
       for (int i = 5; i > 0; i--) {
           priorityQueue.offer(i);
       }
 
       System.out.println("our queue: " + priorityQueue);
 
       System.out.println("Does our queue contain 8?  " + priorityQueue.contains(8));
       System.out.println("Does queue contain 5?  " + priorityQueue.contains(5));
 
       System.out.println("The quantity of queue elements: " + priorityQueue.size());
       Object[] myArray = priorityQueue.toArray();
       System.out.println("print out our array:");
       for (Object name : myArray) {
           System.out.println(name);
       }
   }
}

Il risultato:

our queue: [1, 2, 4, 5, 3]
Does our queue contain 8?  false
Does our queue contain 5?  true
The quantity of queue elements: 5
print out our array:
1
2
4
5
3

Definizione di PriorityQueue Java 8

Se apri la documentazione java 8 di priorityqueue, troverai la definizione successiva: una coda di priorità illimitata basata su un heap di priorità. Gli elementi della coda prioritaria sono ordinati in base al loro ordinamento naturale o da un Comparatore fornito al momento della costruzione della coda, a seconda del costruttore utilizzato. Una coda di priorità non consente elementi nulli. Una coda di priorità che si basa sull'ordinamento naturale non consente inoltre l'inserimento di oggetti non confrontabili (in questo modo potrebbe verificarsi ClassCastException). Mucchio è una parola molto importante qui. Spiega le proprietà dell'ordinamento degli elementi della coda prioritaria.

Il principio del funzionamento di PriorityQueue: Binary Heap

Iniziamo con un esempio. Creiamo due oggetti che implementano l'interfaccia Queue. Uno di loro LinkedList, il secondo — PriorityQueue. Entrambi hanno 5 elementi di Integer (1,2,3,4 e 5) e iniziamo a mettere gli elementi nelle nostre code dal più grande al più piccolo. Quindi, il primo arriva 5, poi 4, 3, 2 e l'ultimo sarà 1. Quindi stampa entrambi gli elenchi per controllare l'ordine.

   Queue<Integer> queueL = new LinkedList<>();
       for (int i = 5; i > 0; i--) {
           queueL.add(i);
       }
       System.out.println("LinkedList Queue (FIFO): " + queueL);
       Queue<Integer> priorityQueue = new PriorityQueue<>();
 
       for (int i = 5; i > 0; i--) {
       priorityQueue.offer(i);
       }
       System.out.println("PriorityQueue: " + priorityQueue)

Il risultato di queste operazioni di codice è il seguente:

LinkedList Queue (FIFO): [5, 4, 3, 2, 1]
PriorityQueue: [1, 2, 4, 5, 3]

Bene, l'ordine della lista collegata è prevedibile e comprensibile. È ordinato secondo il principio FIFO. Abbiamo iniziato con 5, quindi questo elemento è il primo della fila, poi diventa 4 e così via. Cosa possiamo dire dell'ordine di coda prioritario? I documenti hanno affermato che gli elementi della coda prioritaria sono ordinati in base al loro ordinamento naturale o da un comparatore fornito al momento della costruzione della coda. Tuttavia questo ordine non sembra essere "naturale" nel significato di ordinamento lineare. Preferiremmo aspettarci [1, 2, 3, 4, 5], non [1, 2, 4, 5, 3]. Per capire perché l'ordine di recupero è quello che è, dovremmo ricordare quella coda di priorità basata su un heap. Cos'è il mucchio? È una struttura dati basata sull'albero binario. La proprietà principale dell'heap: la priorità di ciascun genitore è maggiore delle priorità dei suoi figli. Lascia che ti ricordi che un albero è chiamato binario completo se ogni genitore non ha più di due figli e il riempimento dei livelli va dall'alto verso il basso (dallo stesso livello - da sinistra a destra). L'heap binario si riorganizza ogni volta che gli elementi vengono aggiunti o rimossi da esso. In caso di min-heap, l'elemento più piccolo va alla radice indipendentemente dall'ordine del suo inserimento. Coda con priorità basata su questo min-heap. Ciò significa che, in caso di elementi della coda di numeri, il primo elemento della coda sarà il minimo di questi numeri. Se elimini la radice, la successiva più piccola diventa una radice.

Passiamo al nostro esempio.

Passaggio 1. Inseriamo "5" nella coda prioritaria. Diventa una radice. Passaggio 2. Aggiungiamo "4" nella coda prioritaria. 4 <5, quindi il nuovo elemento dovrebbe essere più alto di quello vecchio. Il 4 diventa una radice, il 5 è il suo figlio sinistro. Ora la struttura dei dati in Java è [4, 5] Passaggio 3. Aggiungiamo '3'. Temporaneamente diventa figlio destro di una radice (4). Tuttavia, 3 < 4, quindi dovremmo alzarlo. Scambia 3 e 4. Ora abbiamo una struttura come [3, 5, 4] Passaggio 4. Aggiungiamo '2'. Diventa un figlio sinistro di 5. 2<5, quindi scambiali. 2 diventa figlio sinistro di 3, 2 < 3, quindi un altro processo di scambio. Ora abbiamo una struttura [2,3,4,5] Passaggio 5.Aggiungiamo '1'. Viene dal figlio destro del 3 al figlio sinistro del 2, e poi va alla radice. La struttura dei dati del risultato: [1,2,4,5,3] Il processo di rimozione parte da una radice e provoca le procedure inverse. Quindi, prima abbiamo 1 come radice, poi 2, 3, 4 e infine 5. Ecco perché utilizzare l'operazione di rimozione poll()

while (!priorityQueue.isEmpty()) {
           System.out.println(priorityQueue.poll());
       }

abbiamo "ordinato" in output sence lineare:

1
2
3
4
5

Quindi la coda prioritaria potrebbe essere efficace per alcune operazioni. Ci vuole O(log N) tempo per inserire ed eliminare ogni elemento, e puoi ottenere l'elemento minimo in O(1). Ecco l'esempio completo:

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
 
public class PriorityQueueExample {
   public static void main(String[] args) {
 
       Queue<Integer> queueL = new LinkedList<>();
       for (int i = 5; i > 0; i--) {
           queueL.add(i);
       }
       System.out.println("Print our LinkedList Queue (FIFO): " + queueL);
       Queue<Integer> priorityQueue = new PriorityQueue<>();
 
       for (int i = 5; i > 0; i--) {
       priorityQueue.offer(i);
       }
 
       System.out.println("PriorityQueue printing (by iterating, no elements removing): " + priorityQueue);
       System.out.println("Print PriorityQueue using poll() (by retrieval): " );
       while (!priorityQueue.isEmpty()) {
           System.out.println(priorityQueue.poll());
       }
}
}
Print our LinkedList Queue (FIFO): [5, 4, 3, 2, 1]
PriorityQueue printing (by iterating, no elements removing): [1, 2, 4, 5, 3]
Print our  PriorityQueue using poll() (by retrieval): 
1
2
3
4
5

È importante comprendere che le code di priorità si basano su heap binari, quindi non mantengono gli elementi in ordine lineare. Ogni via dalla radice alla foglia è ordinata, ma le vie diverse dalla radice non lo sono. Ciò significa che puoi ottenere l'elemento minimo della coda molto rapidamente.

Cosa dovresti sapere sulla coda prioritaria. Breve elenco

• La coda prioritaria non consente oggetti NULL.
• Puoi aggiungere solo oggetti comparabili in PriorityQueue.
• La coda prioritaria è costruita come un heap minimo, una specie di albero binario. L'elemento minimo è una radice. Gli oggetti della coda prioritaria sono ordinati per impostazione predefinita in ordine naturale.
• Puoi utilizzare Comparator se hai bisogno di ordini personalizzati.
• PriorityQueue non è thread-safe, quindi è meglio utilizzare PriorityBlockingQueue per lavorare in un ambiente simultaneo.
• PriorityQueue fornisce il tempo O(log(n)) per i metodi add e poll e O(1) per ottenere elementi minimi.