Coda prioritaria in java

Supponiamo di offrire servizio a tre diverse persone in piedi davanti a te. La terza persona sembra essere tua amica. Il servizio dovrebbe essere servito all'inizio. Con il primo Come_First-served, la prima persona ha la massima priorità; La seconda persona ha la priorità maggiore; la terza persona, la priorità minore e così via. Non sarai punito, se non osservi il primo arrivo. Hai deciso di servire prima il tuo amico, poi la prima persona, seguita dalla seconda persona. Questo significa che hai dato al tuo amico la massima priorità. Guardando lo scenario dal punto di vista di un robot, la terza posizione aveva la massima priorità.

Il giorno successivo, sono arrivate le stesse tre persone. Questa volta, il tuo amico è nel mezzo. Hai deciso di servirlo per primo, davanti alla persona che è venuta prima, poi alla terza persona, e infine alla prima persona. Quindi, questa volta, secondo il robot, la posizione 2 ha la massima priorità, seguita dalla posizione 3.

Il terzo giorno, il tuo amico è il primo e fai il primo arrivo. La conclusione di chiunque e il robot è che la priorità dipende da chi è preoccupato e dalla posizione di ogni persona. Nota: nella vita reale, la priorità non dipende sempre dal primo arrivo.

Nella programmazione, una coda di priorità binaria è dove il primo elemento ha la massima priorità. Il terzo elemento può avere la priorità maggiore e il secondo elemento, la terza priorità. Le code prioritarie sono di natura binaria. Nota: il primo elemento è sempre la massima priorità in una coda prioritaria. Può anche succedere che il secondo elemento abbia la priorità maggiore e il terzo elemento ha la terza priorità. Nella definizione della coda prioritaria, le priorità della seconda e del terzo elemento potrebbero non essere in ordine decrescente. Questa differenza continua la coda fino all'ultimo elemento, che potrebbe non essere l'articolo minimo prioritario. Tuttavia, sarà tra quelli della più bassa priorità. Questo punto parziale è anche noto come ordine parziale. Quindi, una coda di priorità è una coda di ordinamento parziale, in cui la priorità non è servita per il primo arrivo, sebbene questa sia la regola generale.

Quando si ha a che fare con l'array, il primo COME_FIRST-SERVED è il primo in_first-out, scritto come FIFO. Nel calcolo, la coda è FIFO, mentre la coda prioritaria è un FIFO parziale perché mentre la coda sta discendendo, alcuni articoli hanno priorità maggiori dei loro predecessori vicini. Man mano che la coda prioritaria scende ulteriormente, la distanza tra tali predecessori e le priorità più elevate aumenta.

Una coda prioritaria è implementata come struttura dei dati heap. La prossima domanda è: ciò che è un mucchio? C'è il massimo heap e il mucchio minimo, che sarà discusso in dettaglio di seguito.

Contenuto dell'articolo

• Struttura dei dati heap
• Coda prioritaria in java corretta
• Java Costruzione di una coda prioritaria
• Metodi Java di una coda prioritaria
• Conclusione

Struttura dei dati heap

C'è un heap massimo e c'è un minimo. Con Max-Heap, il primo oggetto è il valore più grande. Man mano che la coda scende, i valori continuano a diminuire, aumentare e generalmente diminuiscono. Con Min Heap, il primo oggetto è il valore più piccolo. Mentre la coda scende, i valori continuano ad aumentare, diminuire e generalmente aumentano. I valori di un mucchio possono essere mantenuti in un array.

Un mucchio binario è dove un nodo (articolo) ha due bambini. Il primo figlio è il bambino sinistro e il secondo figlio è il bambino giusto. Il valore di qualsiasi nodo è chiamato chiave.

Max-heap

L'elenco seguente è un heap massimo che è già parzialmente ordinato e non ha bisogno di ulteriori ordini:

89, 85, 87, 84, 82, 79, 73, 80, 81 ,,, 65, 69

89 è il primo valore all'indice 0. È il nodo radice (radice genitore). È il valore più grande tra tutti i valori. Il suo primo figlio (85) è all'indice 1, il cui indice è uguale a 2 (0) + 1, dove 0 è l'indice del genitore. Il suo secondo figlio (87) è all'indice 2, che è uguale a 2 (0) + 2, dove 0 è l'indice del genitore.

85 è all'indice 1. È un genitore. Il suo primo figlio (84) è all'indice 3, che è uguale a 2 (1) + 1, dove 1 è l'indice del genitore. Il suo secondo figlio (82) è all'indice 4, che è uguale a 2 (1) + 2, dove 1 è l'indice del genitore.

87 è all'indice 2. È un genitore. Il suo primo figlio (79) è all'indice 5, che è uguale a 2 (2) + 1, dove 2 è l'indice del genitore. Il suo secondo figlio (73) è all'indice 6, che è uguale a 2 (2) + 2, dove 2 è l'indice del genitore.

In generale, poiché il conteggio dell'indice inizia da 0, consente di rappresentare l'indice di un genitore dell'array; E così, il figlio (primo) di sinistra di un genitore all'indice I è all'indice 2i + 1; e il suo bambino giusto (secondo), è all'indice 2i + 2. Alcune cellule verso la fine dell'array possono essere vuote; Non devono avere valori.

L'elenco precedente è un buon esempio del contenuto di una coda prioritaria dopo che tutta l'inclusione di elementi è completa. Se il primo elemento viene rimosso, il resto viene riorganizzato per impostare i valori, formando una nuova coda di priorità. In questo modo, la rimozione di tutti gli elementi dall'alto sembrerebbe come se tutti gli elementi fossero ordinati correttamente. Gli elementi possono ancora essere ottenuti così come sono, in un ordine parziale, senza rimuovere alcun elemento.

Min-heap

Min-heap è il contrario di Max-heap.

Coda prioritaria in java corretta

Java ha una classe chiamata priorityQueue, per priorità. Ha molti costruttori e metodi. Di seguito vengono spiegati solo tre costruttori e i metodi più appropriati:

Java Costruzione di una coda prioritaria

Pubblico priorityQueue ()

Questo crea una coda prioritaria senza alcun elemento. La classe, PriorityQueue, è nel Java.util.* pacchetto, che deve essere importato. Il seguente segmento di codice crea una priorità vuota e quindi aggiunge valori non ordinati (nemmeno parzialmente ordinati) alla coda:

PriorityQueue pq = new priorityqueue();
PQ.Aggiungi (69); PQ.Aggiungi (65); PQ.Aggiungi (87); PQ.Aggiungi (79);
PQ.Aggiungi (73); PQ.Aggiungi (84); PQ.Aggiungi (89); PQ.Aggiungi (80);
PQ.Aggiungi (81); PQ.Aggiungi (82); PQ.Aggiungi (85);

Questi numeri sono tutti numeri interi. Sono dall'elenco parzialmente ordinato fornito sopra, ma attualmente sono completamente non mobili quando vengono inseriti. Gli elementi in PQ sono ora parzialmente ordinati in base alla definizione della coda prioritaria in Java.

Public PriorityQueue (PriorityQueue C)

Questo crea una priorità di un altro priorità. Il seguente segmento di codice illustra questo:

PriorityQueue pq = new priorityqueue();
PQ.Aggiungi (69); PQ.Aggiungi (65); PQ.Aggiungi (87); PQ.Aggiungi (79);
PQ.Aggiungi (73); PQ.Aggiungi (84); PQ.Aggiungi (89); PQ.Aggiungi (80);
PQ.Aggiungi (81); PQ.Aggiungi (82); PQ.Aggiungi (85);
PriorityQueue pq1 = new priorityqueue(PQ);

PQ1 è stato creato da PQ. Attualmente ha lo stesso ordine parziale e PQ.

Il terzo metodo del costruttore è illustrato di seguito.

Metodi Java di una coda prioritaria

Public int size ()

Ciò restituisce le dimensioni dell'elenco e non include celle vuote, come illustrato nel seguente codice:

PriorityQueue pq = new priorityqueue();
PQ.Aggiungi (69); PQ.Aggiungi (65); PQ.Aggiungi (87); PQ.Aggiungi (79);
PQ.Aggiungi (73); PQ.Aggiungi (84); PQ.Aggiungi (89); PQ.Aggiungi (80);
PQ.Aggiungi (81); PQ.Aggiungi (82); PQ.Aggiungi (85);
int sz = pq.misurare();
Sistema.fuori.println (sz);

L'output è 11.

Public void foreach (Azione del consumatore)

Questo metodo deve essere utilizzato in modo speciale per copiare tutti i valori nella coda prioritaria nella forma parzialmente ordinata. Il seguente programma illustra questo:

PriorityQueue pq = new priorityqueue();
PQ.Aggiungi (69); PQ.Aggiungi (65); PQ.Aggiungi (87); PQ.Aggiungi (79);
PQ.Aggiungi (73); PQ.Aggiungi (84); PQ.Aggiungi (89); PQ.Aggiungi (80);
PQ.Aggiungi (81); PQ.Aggiungi (82); PQ.Aggiungi (85);
PQ.foreach (articolo -> sistema.fuori.print (elemento + ""));
Sistema.fuori.println ();

Nota il modo in cui è stato realizzato il codice all'interno delle parentesi del metodo Foreach. L'articolo è una variabile fittizia che rappresenta ogni elemento nella coda. Nota l'uso dell'operatore freccia. L'output è:

65 69 84 79 73 87 89 80 81 82 85

L'output è corretto, in un ordine parziale, ma in un ordine ascendente. Questo non è necessariamente l'ordine inverso sopra indicato a causa del modo in cui i valori sono stati inclusi nell'elenco. Cioè, il metodo foreach restituisce l'elenco come un minimo. Per restituire l'elenco in ordine decrescente, utilizzare il seguente costruttore:

Public PriorityQueue (Comparatore Comparatore)

Questo è un costruttore. Il seguente codice mostra come usarlo:

PriorityQueue pq = new priorityqueue((x, y) -> intero.confronta (y, x));
PQ.Aggiungi (69); PQ.Aggiungi (65); PQ.Aggiungi (87); PQ.Aggiungi (79);
PQ.Aggiungi (73); PQ.Aggiungi (84); PQ.Aggiungi (89); PQ.Aggiungi (80);
PQ.Aggiungi (81); PQ.Aggiungi (82); PQ.Aggiungi (85);
PQ.foreach (articolo -> sistema.fuori.print (elemento + ""));

Le x, y sono variabili fittizie che rappresentano i valori minori e meno. Nota che nelle prime parentesi per xey, x viene prima di y. Nella seconda parentesi, y viene prima di x. L'output è:

89 85 87 80 82 69 84 65 79 73 81

Public Boolean Add (e e)

Il numero di elementi in una coda prioritaria può essere aumentato uno per uno. Questo metodo restituisce vero se si è verificata una modifica; e falso altrimenti. Il seguente codice aggiunge il dodicesimo valore pratico alla coda:

PriorityQueue pq = new priorityqueue((x, y) -> intero.confronta (y, x));
PQ.Aggiungi (69); PQ.Aggiungi (65); PQ.Aggiungi (87); PQ.Aggiungi (79);
PQ.Aggiungi (73); PQ.Aggiungi (84); PQ.Aggiungi (89); PQ.Aggiungi (80);
PQ.Aggiungi (81); PQ.Aggiungi (82); PQ.Aggiungi (85); PQ.Aggiungi (70);
PQ.foreach (articolo -> sistema.fuori.print (elemento + ""));

Il valore aggiunto spostarebbe la coda per adattarsi alla sua posizione appropriata, portando ad un po 'di rialdazione delle posizioni degli elementi. L'output è:

89 85 87 80 82 70 84 65 79 73 81 69

PULL PULL ()

Questo metodo recupera e rimuove la testa della coda; o restituisce null, se questa coda è vuota. Ogni volta che la testa viene rimossa, la coda prioritaria si rialzò per avere una nuova testa legittima. Se la testa continua ad essere rimossa, i valori restituiti saranno in ordine ordinato completo. Il seguente codice illustra questo:

PriorityQueue pq = new priorityqueue((x, y) -> intero.confronta (y, x));
PQ.Aggiungi (69); PQ.Aggiungi (65); PQ.Aggiungi (87); PQ.Aggiungi (79);
PQ.Aggiungi (73); PQ.Aggiungi (84); PQ.Aggiungi (89); PQ.Aggiungi (80);
PQ.Aggiungi (81); PQ.Aggiungi (82); PQ.Aggiungi (85); PQ.Aggiungi (70);
PQ.foreach (articolo -> sistema.fuori.Stampa (PQ.sondaggio () + ""));

L'output dal computer dell'autore è:

89 87 85 84 82 81 80 79 73 70 69 65 Eccezione nel thread "Main" Java.util.Exception concurrentModification
a Java.base/java.util.PriorityQueue.foreach (priorityqueue.Java: 984)
a Theclass.Main (TheClass.Java: 11)

Si noti che l'output è di ordine ordinato completo. Questo particolare codice non ha potuto catturare l'eccezione lanciata. Questo problema è lasciato come un esercizio di ricerca per il lettore.

Conclusione

Una coda prioritaria in Java è una coda in cui gli elementi hanno la priorità diversa da FIFO. Una coda prioritaria è in genere un mucchio, che può essere massimo o heap minimo. I valori devono essere dello stesso tipo. Sono conservati in coda in formato heap (ordinamento parziale). Speriamo che tu abbia trovato questo articolo utile. Dai un'occhiata agli altri articoli di suggerimento Linux per suggerimenti e tutorial.