Come usare C++ Priority_queue?

In C++, una coda è una struttura dati di elenco in cui il primo elemento da inserire nell'elenco è il primo elemento da rimuovere, quando deve avvenire la rimozione. Una coda di priorità in C++ è simile, ma ha un certo ordine; è l'elemento con il valore maggiore che viene rimosso per primo. La coda di priorità può ancora essere configurata in modo che sia l'elemento con il valore minimo che viene rimosso per primo. Ogni coda deve avere almeno il Spingere() funzione e il 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 inserito. Per la coda prioritaria, il pop() la funzione rimuove l'elemento con la priorità più alta, che potrebbe essere il più grande o il più piccolo, a seconda dello schema di ordinazione.

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

#includere
#includere
usando lo spazio dei nomi std;

Include la libreria delle code nel programma.

Per continuare la lettura, il lettore dovrebbe avere una conoscenza di base di C++.

Contenuto dell'articolo

Introduzione - vedi sopra
Costruzione di base
Funzioni importanti per i membri
Altre funzioni della coda prioritaria
Dati stringa
Altre costruzioni di code prioritarie
Conclusione

Costruzione di base

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

priority_queue nomecoda;

Con questa sintassi, il valore più grande viene rimosso per primo. Un esempio di istanziazione è:

priority_queue pq;

Il vettore e la deque sono due strutture dati in C++. Una priority_queue può essere creata con uno di essi. La sintassi per creare una coda prioritaria dalla struttura vettoriale è:

priority_queue, confronta> pq;

Un esempio di questa istanza è:

priority_queue, Di meno > pq;

Notare lo spazio tra > e > alla fine della dichiarazione. Questo per evitare confusione con >>. Il codice di confronto predefinito è "meno"", il che significa che il valore più grande, e non necessariamente il primo, verrebbe rimosso per primo. Quindi, l'istruzione di creazione può essere semplicemente scritta come:

priority_queue > pq;

Se il valore minimo deve essere rimosso per primo, l'istruzione deve essere:

priority_queue, maggiore > pq;

Funzioni importanti per i membri

La funzione push()
Questa funzione inserisce un valore, che è il suo argomento, nella coda_priorità. Ritorna vuoto. Il codice seguente lo illustra:

priority_queue pq;
pq.premere(10);
pq.spingere(30);
pq.spingere(20);
pq.spinta(50);
pq.spingere(40);

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

La funzione pop()
Questa funzione rimuove da priority_queue il valore con la priorità più alta. Se il codice di confronto è "maggiore"", quindi rimuoverà l'elemento con il valore più piccolo. Se richiamato di nuovo, rimuove l'elemento successivo con il valore più piccolo del resto; richiamato di nuovo, rimuove il successivo valore più piccolo presente, e così via. Ritorna vuoto. Il codice seguente lo illustra:

priority_queue, maggiore > pq;
pq.push('a'); pq.premere('c'); pq.push('b'); pq.push('e'); pq.push('d');

Nota 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 con la priorità più alta, ma non lo restituisce, come pop() è una funzione nulla. Usa il superiore() funzione per conoscere il valore della priorità più alta che deve essere rimosso successivamente. Il superiore() la funzione restituisce una copia del valore di priorità più alta in priority_queue. Il codice seguente, dove il valore successivo di priorità più alta è il valore minimo, lo illustra

priority_queue, maggiore > pq;
pq.push('a'); pq.premere('c'); pq.premere('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 empty()
Se un programmatore utilizza il superiore() funzione su una priority_queue vuota, dopo la corretta compilazione, riceverà un messaggio di errore del tipo:

Errore di segmentazione (core dump)

Quindi, controlla sempre se la coda di priorità non è vuota prima di utilizzare il superiore() funzione. Il vuoto() la funzione membro restituisce un bool, true, se la coda è vuota e false se la coda non è vuota. Il codice seguente lo illustra:

priority_queue pq;
int i1 = 10; int i2 = 30; int i3 = 20; int i4 = 50; int i5 = 40;
pq.premere(i1); pq.premere(i2); pq.spingere(i3); pq.premere(i4); pq.premere(i5);
mentre(!pq.vuoto())

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

cout << '\n';

Altre funzioni della coda prioritaria

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

priority_queue pq;
int i1 = 10; int i2 = 30; int i3 = 20; int i4 = 50; int i5 = 40;
pq.premere(i1); pq.premere(i2); pq.spingere(i3); pq.premere(i4); pq.premere(i5);
int len = pq.dimensione();
cout << len << '\n';

L'uscita è 5.

La funzione swap()
Se due priority_queues sono dello stesso tipo e dimensione, possono essere scambiate da questa funzione, come mostra il codice seguente:

priority_queue pq1;
int i1 = 10; int i2 = 30; int i3 = 20; int i4 = 50; int i5 = 40;
pq1.premere(i1); pq1.premere(i2); pq1.spingere(i3); pq1.premere(i4); pq1.premere(i5);
priority_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.scambiare(pqA);
mentre(!pq1.vuoto())

cout << pq1.top() << ";
pq1.pop();
cout<<'\n';
mentre(!pqA.vuoto())

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

L'uscita è:

5 4 3 2 1
50 40 30 20 10

La funzione emplace()
Il posto() la funzione è simile alla funzione push. Il codice seguente lo illustra:

priority_queue pq1;
int i1 = 10; int i2 = 30; int i3 = 20; int i4 = 50; int i5 = 40;
pq1.posto(i1); pq1.posto(i2); pq1.posto(i3); pq1.posto(i4); pq1.posto(i5);
mentre(!pq1.vuoto())

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

L'uscita è:

50 40 30 20 10

Dati stringa

Quando si confrontano le stringhe, è necessario utilizzare la classe stringa e non l'uso diretto dei letterali stringa perché confronterebbe i puntatori e non le stringhe effettive. Il codice seguente mostra come viene utilizzata la classe stringa:

#includere
priority_queue pq1;
string s1 = string("penna"), s2 = string("matita"), s3 = string("libro degli esercizi"), s4 = string("libro di testo"), s5 = string("righello");
pq1.premere(s1); pq1.spingere(s2); pq1.spingere(s3); pq1.spingere(s4); pq1.spingere(s5);
mentre(!pq1.vuoto())

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

L'uscita è:

quaderno per libri di testo righello matita penna

Altre costruzioni di code prioritarie

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

#includere
vettore vtr = 10, 30, 20, 50, 40;
priority_queue pq(vtr.begin(), vtr.fine());
mentre(!pq.vuoto())

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

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

Per rendere il valore minimo la priorità, la dichiarazione per il costruttore sarebbe:

priority_queue, maggiore>int> > pq(vtr.begin(), vtr.fine());

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

int arr[] = 10, 30, 20, 50, 40;
priority_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 di costruzione prendono i puntatori di inizio e fine dell'array. arr restituisce il puntatore iniziale, "arr+5" restituisce il puntatore appena oltre l'array e 5 è la dimensione dell'array. Il tipo di dati per l'array e il tipo di dati per priority_queue devono essere gli stessi.

Per rendere il valore minimo la priorità, la dichiarazione per il costruttore sarebbe:

priority_queue, maggiore > pq(arr, arr+5);

Nota: in C++, priority_queue è in realtà chiamato adattatore, non solo contenitore.

Codice di confronto personalizzato

Avere tutti i valori nella coda di priorità crescenti o tutti discendenti non è l'unica opzione per la coda di priorità. Ad esempio, un elenco di 11 numeri interi per un heap 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 meno di 88. Il resto dei numeri è inferiore a questi tre numeri, ma non proprio in ordine. 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 di max-heap - vedi più avanti. Per fornire un tale schema per priority_queue, il programmatore deve fornire il proprio codice di confronto - vedere più avanti.

Conclusione

Una priority_queue C++ è una coda first-in-first-out. La funzione membro, Spingere(), aggiunge un nuovo valore alla coda. La funzione membro, superiore(), legge il valore più alto nella coda. La funzione membro, pop(), rimuove senza restituire il valore superiore della coda. La funzione membro, vuoto(), controlla se la coda è vuota. Tuttavia, priority_queue differisce dalla coda, in quanto segue un algoritmo di priorità. Può essere il più grande, dal primo all'ultimo, o il meno, dal primo all'ultimo. I criteri (algoritmo) possono anche essere definiti dal programmatore.