Come utilizzare C ++ priority_queue?

In C ++, una coda è una struttura di dati dell'elenco in cui il primo elemento da inserire nell'elenco è il primo elemento da rimuovere, quando si verifica la rimozione. Una coda prioritaria in C ++ è simile, ma ha un po 'di ordinazione; È l'elemento con il massimo valore che viene rimosso per primo. La coda prioritaria può ancora essere configurata in modo che sia l'elemento con il valore minimo che viene rimosso per primo. Qualsiasi coda deve avere almeno il spingere() funzione e pop() funzione. IL spingere() La funzione aggiunge un nuovo elemento sul retro. Per la coda normale, il pop() La funzione rimuove il primo elemento mai spinto. Per la coda prioritaria, il pop() La funzione rimuove l'elemento con la massima priorità, che potrebbe essere la più grande o più piccola, a seconda dello schema di ordinazione.

Per utilizzare C ++ Priority_Queue, il programma dovrebbe iniziare con il codice come:

#includere
#includere
Utilizzo dello spazio dei nomi std;

Include la libreria di code nel programma.

Per continuare a leggere, il lettore avrebbe dovuto avere una conoscenza di base di C++.

Contenuto dell'articolo

• Costruzione di base
• Importanti funzioni dei membri
• Altre funzioni di coda prioritaria
• Dati di stringa
• Altre costruzioni in coda prioritaria
• Conclusione

Costruzione di base

La struttura dei dati deve essere costruita prima di poter essere utilizzata. Costruzione qui significa istanziare un oggetto dalla classe di coda della biblioteca. L'oggetto in coda deve quindi avere un nome dato dal programmatore. La sintassi più semplice per creare una coda prioritaria è:

priorità_queue Queuename;

Con questa sintassi, il valore maggiore viene rimosso per primo. Un esempio dell'istanziazione è:

priorità_queue PQ;

O

priorità_queue PQ;

Il vettore e il deque sono due strutture di dati in c++. Un priority_queue può essere creato con uno di essi. La sintassi per creare una coda prioritaria dalla struttura vettoriale è:

priorità_queue, confronta> pq;

Un esempio di questa istanza è:

priorità_queue, meno > PQ;

Notare il divario tra> e> alla fine della dichiarazione. Questo per prevenire la confusione con >>. Il codice di confronto predefinito è "inferiore", il che significa che il più grande, e non necessariamente il primo valore, verrebbe rimosso per primo. Quindi, la dichiarazione di creazione può essere semplicemente scritta come:

priorità_queue > PQ;

Se il valore minimo deve essere rimosso prima, allora l'istruzione deve essere:

priorità_queue, maggiore > PQ;

Importanti funzioni dei membri

La funzione push ()
Questa funzione spinge un valore, che è il suo argomento, nella priorità_queue. Restituisce vuoto. Il seguente codice illustra questo:

priorità_queue PQ;
PQ.push (10);
PQ.push (30);
PQ.push (20);
PQ.push (50);
PQ.push (40);

Questa priorità_queue ha ricevuto 5 valori interi nell'ordine di 10, 30, 20, 50, 40. Se tutti questi elementi devono essere espulsi dalla coda prioritaria, allora usciranno nell'ordine di 50, 40, 30, 20, 10.

La funzione pop ()
Questa funzione rimuove da priorità_queue il valore con la massima priorità. Se il codice di confronto è "maggiore", rimuoverà l'elemento con il valore più piccolo. Se chiamato di nuovo, rimuove l'elemento successivo con il valore più piccolo del resto; Chiamato di nuovo, rimuove il prossimo valore più piccolo presente, e così via. Restituisce vuoto. Il seguente codice illustra questo:

priorità_queue, maggiore > PQ;
PQ.push ('a');
PQ.push ('c');
PQ.push ('b');
PQ.push ('e');
PQ.push ('d');

Si noti che per chiamare una funzione membro, il nome dell'oggetto deve essere seguito da un punto e quindi dalla funzione.

La funzione top ()
IL pop() la funzione rimuove il valore successivo della massima priorità, ma non la restituisce, come pop() è una funzione vuota. Usa il superiore() funzione per conoscere il valore della massima priorità che deve essere rimossa successivamente. IL superiore() La funzione restituisce una copia del valore della massima priorità nella priorità. Il seguente codice, in cui il valore successivo della massima priorità è il minimo valore, illustra questo

priorità_queue, maggiore > PQ;
PQ.push ('a'); PQ.push ('c'); PQ.push ('b'); PQ.push ('e'); PQ.push ('d');
char ch1 = pq.superiore(); PQ.pop();
char ch2 = pq.superiore(); PQ.pop();
char ch3 = pq.superiore(); PQ.pop();
char ch4 = pq.superiore(); PQ.pop();
char ch5 = pq.superiore(); PQ.pop();
cout<

L'output è 'a "b" c "d" e'.

La funzione vuota ()
Se un programmatore utilizza il file superiore() Funzione su una priorità vuota_queue, dopo la raccolta riuscita, riceverebbe un messaggio di errore come:

Guasto di segmentazione (core scaricato)

Quindi, controlla sempre se la coda prioritaria non è vuota prima di usare il superiore() funzione. IL vuoto() La funzione membro restituisce un bool, vero, se la coda è vuota e falsa se la coda non è vuota. Il seguente codice illustra questo:

priorità_queue PQ;
int i1 = 10; int i2 = 30; int i3 = 20; int i4 = 50; int i5 = 40;
PQ.push (i1); PQ.push (i2); PQ.push (i3); PQ.push (i4); PQ.push (i5);
Mentre(!PQ.vuoto())

cout << pq.top() << ";
PQ.pop();

cout << '\n';

Altre funzioni di coda prioritaria

La funzione size ()
Questa funzione restituisce la lunghezza della coda prioritaria, come illustra il seguente codice:

priorità_queue PQ;
int i1 = 10; int i2 = 30; int i3 = 20; int i4 = 50; int i5 = 40;
PQ.push (i1); PQ.push (i2); PQ.push (i3); PQ.push (i4); PQ.push (i5);
int len ​​= pq.misurare();
cout << len << '\n';

L'output è 5.

La funzione Swap ()
Se due priorità_queues sono dello stesso tipo e dimensioni, possono essere scambiati da questa funzione, come mostra il seguente codice:

priorità_queue PQ1;
int i1 = 10; int i2 = 30; int i3 = 20; int i4 = 50; int i5 = 40;
PQ1.push (i1); PQ1.push (i2); PQ1.push (i3); PQ1.push (i4); PQ1.push (i5);
priorità_queue PQA;
int it1 = 1; int it2 = 3; int it3 = 2; int it4 = 5; int it5 = 4;
pqa.push (it1); pqa.push (it2); pqa.push (it3); pqa.push (it4); pqa.push (it5);
PQ1.swap (pqa);
Mentre(!PQ1.vuoto())

cout << pq1.top() << ";
PQ1.pop();
Cout<<'\n';
Mentre(!pqa.vuoto())

cout << pqA.top() << ";
pqa.pop();
Cout<<'\n';

L'output è:

5 4 3 2 1
50 40 30 20 20 10

La creazione di emplace ()
IL emplace () La funzione è simile alla funzione push. Il seguente codice illustra questo:

priorità_queue PQ1;
int i1 = 10; int i2 = 30; int i3 = 20; int i4 = 50; int i5 = 40;
PQ1.emplace (i1);
PQ1.emplace (i2);
PQ1.emplace (i3);
PQ1.emplace (i4);
PQ1.emplace (i5);
Mentre(!PQ1.vuoto())

cout << pq1.top() << ";
PQ1.pop();
Cout<<'\n';

L'output è:

50 40 30 20 20 10

Dati di stringa

Quando si confrontano le stringhe, la classe di stringa dovrebbe essere usata e non l'uso diretto dei letterali delle stringhe perché confronterebbe i puntatori e non le stringhe effettive. Il seguente codice mostra come viene utilizzata la classe String:

#includere
priorità_queue PQ1;
String s1 = string ("penna"),
S2 = String ("Pencil"),
s3 = string ("libro di allenamento"),
s4 = string ("libro di testo"),
s5 = string ("righello");
PQ1.push (S1);
PQ1.push (S2);
PQ1.push (S3);
PQ1.push (S4);
PQ1.push (S5);
Mentre(!PQ1.vuoto())

cout << pq1.top() << " ";
PQ1.pop();
Cout<<'\n';

L'output è:

libro di esercizi del righello del sovrano di testo

Altre costruzioni in coda prioritaria

Creazione esplicita da un vettore
Una coda prioritaria può essere creata esplicitamente da un vettore come mostra il seguente codice:

#includere
vettore vtr = 10, 30, 20, 50, 40;
priorità_queue PQ (VTR.inizio (), vtr.FINE());
Mentre(!PQ.vuoto())

cout << pq.top() << ";
PQ.pop();
Cout<<'\n';

L'uscita è: 50 40 30 20 10. Questa volta, anche l'intestazione vettoriale deve essere inclusa. Gli argomenti per la funzione del costruttore prendono i puntatori di inizio e fine del vettore. Il tipo di dati per il vettore e il tipo di dati per priority_queue deve essere lo stesso.

Al fine di rendere il minimo valore la priorità, la dichiarazione per il costruttore sarebbe:

priorità_queue, maggiore> int>> pq (VTR.inizio (), vtr.FINE());

Creazione esplicita da un array
Una coda prioritaria può essere creata esplicitamente da un array come mostra il seguente codice:

int arr [] = 10, 30, 20, 50, 40;
priorità_queue PQ (arr, arr+5);
Mentre(!PQ.vuoto())

cout << pq.top() << ";
PQ.pop();
Cout<<'\n';

L'uscita è: 50 40 30 20 10. Gli argomenti per la funzione del costruttore prendono i puntatori di inizio e fine dell'array. ARR restituisce il puntatore di avvio, "arr+5" restituisce il puntatore appena oltre l'array e 5 ha la dimensione dell'array. Il tipo di dati per l'array e il tipo di dati per priority_queue deve essere lo stesso.

Al fine di rendere il minimo valore la priorità, la dichiarazione per il costruttore sarebbe:

priorità_queue, maggiore > PQ (arr, arr+5);

Nota: in C ++, la priorità_queue è effettivamente chiamata adattatore, non solo un contenitore.

Codice di confronto personalizzato

Avere tutti i valori nella coda prioritaria ascendente o tutta la decrescenza non è l'unica opzione per la coda prioritaria. Ad esempio, un elenco di 11 numeri interi per un mucchio massimo è:

88, 86, 87, 84, 82, 79,74, 80, 81 ,,, 64, 69

Il valore più alto è 88. Questo è seguito da due numeri: 86 e 87, che sono inferiori a 88. Il resto dei numeri è inferiore a questi tre numeri, ma non in realtà. Ci sono due celle vuote nell'elenco. I numeri 84 e 82 sono inferiori a 86. I numeri 79 e 74 sono inferiori a 87. I numeri 80 e 81 sono inferiori a 84. I numeri 64 e 69 sono inferiori a 79.

Il posizionamento dei numeri segue i criteri massimi di heap - vedi più tardi. Al fine di fornire tale schema per priorità_queue, il programmatore deve fornire il proprio codice di confronto - vedere più tardi.

Conclusione

A C ++ Priority_Queue è una coda del primo in primo piano. La funzione membro, spingere(), Aggiunge un nuovo valore alla coda. La funzione membro, superiore(), Legge il valore superiore in coda. La funzione membro, pop(), rimuove senza restituire il valore superiore della coda. La funzione membro, vuoto(), controlla se la coda è vuota. Tuttavia, la priorità_queue differisce dalla coda, in questo segue un algoritmo prioritario. Può essere più grande, dal primo all'ultimo, o meno, dal primo all'ultimo. I criteri (algoritmo) possono anche essere definiti dal programmatore.