java priority queue tutorial implementation examples
Questo tutorial spiega la Java Priority Queue e concetti correlati come Comparator, Min e Max Priority Queue insieme alla sua implementazione con esempi:
La struttura dei dati della coda di priorità è una coda speciale in cui gli elementi sono presenti non secondo l'ordine FIFO ma secondo gli elementi naturali o qualsiasi comparatore personalizzato utilizzato durante la creazione della coda.
=> Dai un'occhiata alla guida per principianti di Java qui.
Cosa imparerai:
Coda prioritaria in Java
In Priority Queue, la parte anteriore della coda ha il minor numero di elementi secondo l'ordine naturale e la parte posteriore è puntata all'elemento più grande nella coda.
Di seguito è riportato un esempio di coda prioritaria composta da numeri.
amministratore informatica intervista domande e risposte
Pertanto, quando un elemento viene rimosso dalla coda di priorità mostrata sopra, sarà l'elemento meno importante.
Allo stesso modo, per una coda con priorità alfabetica, verranno considerati i valori ASCII e gli elementi della coda verranno ordinati secondo i valori ASCII.
Di seguito sono elencate alcune delle principali caratteristiche della PriorityQueue:
- PriorityQueue è una coda non associata.
- PriorityQueue non consente valori null.
- Per oggetti non confrontabili, non possiamo creare una coda di priorità.
- PriorityQueue eredita dalle classi come AbstractQueue, AbstractCollection, Collection e Object.
- L'inizio o la parte anteriore della coda contiene l'elemento minimo secondo l'ordine naturale.
- L'implementazione della coda prioritaria non è thread-safe. Quindi, se desideriamo un accesso sincronizzato, dovremmo usare PriorityBlockingQueue.
La classe PriorityQueue eredita Java Queue Interface ed è una parte del pacchetto java.util.
Di seguito viene fornita la dichiarazione generale della classe PriorityQueue:
public class PriorityQueue extends AbstractQueue implements SerializableIl diagramma seguente mostra la gerarchia delle classi per la classe PriorityQueue.
Complessità temporale della coda prioritaria
- La complessità temporale di Priority Queue per i metodi di inserimento (accodamento) e cancellazione (rimozione dalla coda) è O (log (n)).
- Priority Queue ha una complessità temporale lineare per i metodi di rimozione e contiene.
- I metodi che recuperano gli elementi della coda prioritaria hanno una complessità temporale costante.
Esempio di coda prioritaria in Java
Il programma seguente mostra una semplice PriorityQueue in Java. Creiamo un oggetto della classe PriorityQueue, aggiungiamo valori ad esso e quindi visualizziamo il contenuto della coda utilizzando Iterator.
import java.util.*; class Main{ public static void main(String args()){ PriorityQueue cities_queue=new PriorityQueue(); //initialize the PriorityQueue with values cities_queue.add('Sydney'); cities_queue.add('Venice'); cities_queue.add('New York'); cities_queue.add('California'); cities_queue.add('Melbourne'); //print the head of the PriorityQueue System.out.println('PriorityQueue Head:'+cities_queue.element()); //Define the iterator for PriorityQueue and print its elements System.out.println('
PriorityQueue contents:'); Iterator iter=cities_queue.iterator(); while(iter.hasNext()){ System.out.print(iter.next() + ' '); } } } Produzione:
Metodi API Java Priority Queue
Costruttori:
| Prototipo del costruttore | Descrizione | |
|---|---|---|
| sbirciare | E sbircia () | Restituisce l'inizio della coda senza eliminare l'elemento. |
| PriorityQueue () | Un costruttore predefinito che crea un oggetto PriorityQueue con capacità iniziale pari a 1. | |
| PriorityQueue (Collezione c) | Crea un oggetto PriorityQueue con gli elementi iniziali della raccolta data c. | |
| PriorityQueue (int initialCapacity) | Crea un oggetto PriorityQueue con la 'capacità iniziale' data. Gli elementi sono ordinati secondo l'ordine naturale. | |
| PriorityQueue (int initialCapacity, Comparator comparator) | Crea un oggetto PriorityQueue con la 'capacità iniziale' data. Gli elementi sono ordinati in base al comparatore fornito. | |
| PriorityQueue (PriorityQueue c) | Crea un oggetto PriorityQueue da un altro oggetto PriorityQueue fornito da c. | |
| PriorityQueue (SortedSet c) | Crea un oggetto PriorityQueue da un SortedSet fornito da c. |
Metodi
| Metodo | Metodo Prototipo | Descrizione |
|---|---|---|
| Inserisci | booleano add (E e) | Aggiunge l'elemento e a PriorityQueue. |
| chiaro | void clear () | Cancella PriorityQueue eliminando tutti gli elementi. |
| comparatore | Comparatorcomparator () | Restituisce un comparatore personalizzato utilizzato per l'ordinamento degli elementi nella coda. |
| contiene | booleano contiene (Oggetto o) | Controlla se PriorityQueue contiene l'elemento specificato o. Restituisce vero se sì. |
| iteratore | Iteratoriterator () | Metodo per ottenere un iteratore per la PriorityQueue data. |
| offrire | offerta booleana (E e) | Inserire l'elemento e dato in PriorityQueue. |
| sondaggio | E sondaggio () | Rimuove e restituisce l'inizio della coda. Restituisce null se la coda è vuota. |
| rimuovere | booleano remove (Object o) | Rimuove un'istanza di un dato elemento o se è presente nella coda. |
| taglia | int size () | Restituisce la dimensione o il numero di elementi in questa PriorityQueue. |
| toArray | Object () toArray () | Restituisce una rappresentazione in matrice della PriorityQueue data. |
| toArray | T () toArray (T () a) | Restituisce una rappresentazione di matrice per la coda di priorità data con lo stesso tipo di runtime dell'array specificato a. |
Implementazione in Java
Dimostriamo i metodi precedenti di PriorityQueue utilizzando un programma Java.
import java.util.*; class Main { public static void main(String args()) { // Creating empty priority queue PriorityQueue numQueue = new PriorityQueue(); // add elements to numQueue using add() numQueue.add('Five'); numQueue.add('One'); numQueue.add('Seven'); numQueue.add('Three'); numQueue.add('Eleven'); numQueue.add('Nine'); // Print the head element using Peek () method System.out.println('Head element using peek method:' + numQueue.peek()); // Printing all elements System.out.println('
The PriorityQueue elements:'); Iterator iter1 = numQueue.iterator(); while (iter1.hasNext()) System.out.print(iter1.next() + ' '); // remove head with poll () numQueue.poll(); System.out.println('
After removing an element' + 'with poll function:'); Iterator iter2 = numQueue.iterator(); while (iter2.hasNext()) System.out.print(iter2.next() + ' '); // Remove 'Three' using remove () numQueue.remove('Three'); System.out.println('
Element 'Three' with' + ' remove function:'); Iterator iter3 = numQueue.iterator(); while (iter3.hasNext()) System.out.print(iter3.next() + ' '); // Check if an element is present in PriorityQueue using contains() boolean ret_val = numQueue.contains('Five'); System.out.println('
Priority queue contains 'Five' ' + 'or not?: ' + ret_val); // get array equivalent of PriorityQueue with toArray () Object() numArr = numQueue.toArray(); System.out.println('
Array Contents: '); for (int i = 0; i Produzione:
c ++ pausa per 1 secondo
Coda prioritaria in Java 8
Java 8 aggiunge un altro metodo alla classe PriorityQueue, ovvero 'spliterator ()'.
I dettagli di questo metodo sono forniti di seguito.
Nome metodo: splitter
Prototipo del metodo: public final Spliterator spliterator ()
Descrizione del metodo: Questo metodo crea uno spliterator sugli elementi PriorityQueue. Questo spliterator è tardivo e veloce.
Comparatore code prioritarie
Come già accennato, gli elementi PriorityQueue sono naturalmente ordinati. Se vogliamo modificare l'ordine, dobbiamo specificare un comparatore e utilizzarlo durante la creazione dell'oggetto PriorityQueue. PriorityQueue utilizza quindi questo comparatore per ordinare i suoi elementi.
Il seguente programma Java mostra l'uso del comparatore personalizzato per l'ordinamento degli elementi. In questo programma, definiamo un nuovo comparatore personalizzato all'interno del quale sovrascriviamo il metodo 'compare'. Il metodo di confronto viene utilizzato per ordinare gli elementi di PriorityQueue in base alla lunghezza.
import java.util.*; public class Main { public static void main(String() args) { // A custom comparator that compares two Strings by their length. Comparator customComparator = new Comparator() { @Override public int compare(String s1, String s2) { return s1.length() - s2.length(); } }; // Create a Priority Queue with a custom Comparator PriorityQueue colorsPriorityQueue = new PriorityQueue(customComparator); // Add items to a Priority Queue colorsPriorityQueue.add('Red'); colorsPriorityQueue.add('Green'); colorsPriorityQueue.add('Blue'); colorsPriorityQueue.add('Cyan'); colorsPriorityQueue.add('Magenta'); colorsPriorityQueue.add('Yellow'); // Printing all elements System.out.println('
The PriorityQueue elements with custom Comparator:'); Iterator iter1 = colorsPriorityQueue.iterator(); while (iter1.hasNext()) System.out.print(iter1.next() + ' '); } } Produzione:
Coda con priorità minima in Java
L'ordine naturale della coda prioritaria ha l'elemento più piccolo o più piccolo all'inizio della coda e quindi l'ordine è crescente. Questa è chiamata 'coda di priorità minima' con ordine crescente di elementi.
Il programma Java di seguito mostra l'implementazione di Min Priority Queue in Java.
import java.util.*; class Main{ public static void main(String args()){ //declare a PriorityQueue object with default ordering PriorityQueue pq = new PriorityQueue(); //add element to the PriorityQueue pq.add(8); pq.add(6); pq.add(4); pq.add(2); pq.add(12); pq.add(10); //display the min PriorityQueue System.out.println('The min Priority Queue (natural ordering) contents:'); Integer val = null; while( (val = pq.poll()) != null) { System.out.print(val + ' '); } } } Produzione:
Coda priorità massima in Java
Mentre la coda con priorità minima ha elementi in ordine crescente, la coda con priorità massima ha gli elementi in ordine decrescente, ovvero la testa della coda con priorità massima restituirà l'elemento più grande nella coda.
Il programma Java riportato di seguito mostra la coda di priorità massima in Java.
import java.util.*; class Main{ public static void main(String args()){ //declare a PriorityQueue object with custom comparator to generate max PQ PriorityQueue pq = new PriorityQueue(new Comparator() { public int compare(Integer lhs, Integer rhs) { if (lhs Produzione:
Come mostrato nel programma precedente, per cambiare l'ordine naturale degli elementi nella coda di priorità, dobbiamo definire un comparatore personalizzato.
Domande frequenti
D # 1) Cos'è la coda prioritaria in Java?
Risposta: Una coda speciale in cui tutti gli elementi della coda sono ordinati secondo l'ordine naturale o utilizzando un comparatore personalizzato è chiamata coda prioritaria. Non segue l'ordine FIFO.
D # 2) Come si imposta una coda con priorità massima in Java?
quale delle seguenti affermazioni è vera per un test di sistema?
Risposta: Possiamo impostare una coda di priorità massima in Java utilizzando un comparatore personalizzato in modo che la testa della coda restituisca l'elemento più grande nella coda.
D # 3) La coda Priority consente duplicati Java?
Risposta: Sì. Priority Queue consente valori duplicati.
D # 4) La coda Java Priority è massima o minima?
Risposta: Per impostazione predefinita, la coda di priorità in Java è la coda di priorità minima con ordinamento naturale. Per renderlo massimo, dobbiamo utilizzare un comparatore personalizzato in modo che il capo della coda restituisca l'elemento più grande nella coda.
D # 5) È stata ordinata una coda prioritaria?
Risposta: Per impostazione predefinita, il capo della coda viene ordinato e la coda prioritaria ha l'elemento minimo come capo. Il resto degli elementi viene ordinato quando richiesto.
Conclusione
Questo completa il tutorial sulle code prioritarie in Java. Priority Queue implementa un'interfaccia di coda ed è una coda speciale in cui gli elementi vengono ordinati secondo l'ordine naturale. Non segue l'ordine FIFO. Per modificare l'ordine naturale della coda di priorità, possiamo utilizzare il comparatore personalizzato.
Le code prioritarie vengono utilizzate principalmente per la pianificazione della stampante, la pianificazione delle attività della CPU, ecc. Anche l'heap (minimo o massimo) viene implementato utilizzando le code prioritarie.
=> Leggere attraverso la serie di formazione Easy Java.
Lettura consigliata
- Priorità Struttura Dati Coda In C ++ Con Illustrazione
- Coda prioritaria in AWL
- Java Queue - Metodi di coda, implementazione di code con esempi
- Struttura dei dati della coda circolare C ++: implementazione e applicazioni
- Double Ended Queue (Deque) in C ++ con esempi
- Struttura dei dati della coda in C ++ con illustrazione
- Pile e code in STL
- Tutorial JAVA per principianti: oltre 100 tutorial video Java pratici
