UN Coda con priorità C++ è un tipo di adattatore contenitore, progettato specificamente in modo tale che il primo elemento della coda sia il più grande o il più piccolo di tutti gli elementi nella coda e gli elementi siano in ordine non crescente o non decrescente (quindi possiamo vedere che ciascuno elemento della coda ha una priorità {ordine fisso}).
In C++ STL, l'elemento superiore è sempre il maggiore per impostazione predefinita. Possiamo anche cambiarlo nell'elemento più piccolo in alto. Le code prioritarie vengono create in cima all'heap massimo e utilizzano un array o un vettore come struttura interna. In parole povere, Coda prioritaria STL è l'implementazione del C++
// C++ program to demonstrate the use of priority_queue> #include> #include> using> namespace> std;> // driver code> int> main()> {> >int> arr[6] = { 10, 2, 4, 8, 6, 9 };> >// defining priority queue> >priority_queue<>int>>pq;> >// printing array> >cout <<>'Array: '>;> >for> (>auto> i : arr) {> >cout << i <<>' '>;> >}> >cout << endl;> >// pushing array sequentially one by one> >for> (>int> i = 0; i <6; i++) {> >pq.push(arr[i]);> >}> >// printing priority queue> >cout <<>'Priority Queue: '>;> >while> (!pq.empty()) {> >cout << pq.top() <<>' '>;> >pq.pop();> >}> >return> 0;> }> |
>
>Produzione
Array: 10 2 4 8 6 9 Priority Queue: 10 9 8 6 4 2>
Coda con priorità heap massima (schema predefinito)
Come creare un heap minimo per la coda prioritaria?
Come abbiamo visto in precedenza, una coda con priorità viene implementata come heap massimo per impostazione predefinita in C++ ma ci fornisce anche un'opzione per cambiarla in heap minimo passando un altro parametro durante la creazione di una coda con priorità.
Sintassi:
priority_queue gq;>
Dove,
- 'int' è il tipo di elementi che desideri memorizzare nella coda di priorità. In questo caso, è un numero intero. Puoi sostituire int con qualsiasi altro tipo di dati di cui hai bisogno. 'vettore' è il tipo di contenitore interno utilizzato per archiviare questi elementi. std::priority_queue non è un contenitore in sé ma un adottante del contenitore. Avvolge altri contenitori. In questo esempio, stiamo usando a vettore , ma potresti scegliere un contenitore diverso che supporti i metodi front(), push_back() e pop_back().
- ' maggiore ‘ è una funzione di confronto personalizzata. Ciò determina come vengono ordinati gli elementi all'interno della coda di priorità. In questo esempio specifico, maggiore imposta a min-heap . Ciò significa che l'elemento più piccolo sarà in cima alla coda.
Nel caso del max heap, non abbiamo dovuto specificarli poiché i valori predefiniti per questi sono già adatti per il max heap.
Esempio:
C++
// C++ program to demonstrate> // min heap for priority queue> #include> #include> using> namespace> std;> void> showpq(> >priority_queue<>int>, vector<>int>>, maggiore<>int>>>g)> {> >while> (!g.empty()) {> >cout <<>' '> << g.top();> >g.pop();> >}> >cout <<>'
'>;> }> void> showArray(>int>* arr,>int> n)> {> >for> (>int> i = 0; i cout << arr[i] << ' '; } cout << endl; } // Driver Code int main() { int arr[6] = { 10, 2, 4, 8, 6, 9 }; priority_queue |
>
>Produzione
Array: 10 2 4 8 6 9 Priority Queue : 2 4 6 8 9 10>
Coda con priorità heap minima
Nota: La sintassi di cui sopra potrebbe essere difficile da ricordare, quindi in caso di valori numerici, possiamo moltiplicare i valori per -1 e utilizzare max heap per ottenere l'effetto di min heap. Non solo possiamo utilizzare il metodo di ordinamento personalizzato sostituendo maggiore con funzione comparatore personalizzato.
Metodi di coda prioritaria
Il seguente elenco di tutti i metodi della classe std::priority_queue:
| Metodo | Definizione |
|---|---|
| priorità_coda::vuoto() | Restituisce se la coda è vuota. |
| priorità_queue::dimensione() | Restituisce la dimensione della coda. |
| priorità_queue::top() | Restituisce un riferimento all'elemento più in alto della coda. |
| priorità_queue::push() | Aggiunge l'elemento 'g' alla fine della coda. |
| priorità_queue::pop() | Elimina il primo elemento della coda. |
| priorità_queue::swap() | Utilizzato per scambiare il contenuto di due code purché le code debbano essere dello stesso tipo, sebbene le dimensioni possano differire. |
| priorità_queue::emplace() | Utilizzato per inserire un nuovo elemento nel contenitore della coda di priorità. |
| priorità_coda tipo_valore | Rappresenta il tipo di oggetto archiviato come elemento in una priorità_queue. Funziona come sinonimo del parametro template. |
Operazioni sulla coda con priorità in C++
1. Inserimento e rimozione di elementi di una coda prioritaria
IL spingere() viene utilizzato per inserire un elemento nella coda di priorità. Per rimuovere un elemento dalla coda di priorità il pop() viene utilizzato il metodo perché rimuove l'elemento con la priorità più alta.
Di seguito è riportato il programma C++ per varie funzioni nella coda di priorità:
C++
tipi di dati SQL
// C++ Program to demonstrate various> // method/function in Priority Queue> #include> #include> using> namespace> std;> // Implementation of priority queue> void> showpq(priority_queue<>int>>gq)> {> >priority_queue<>int>>g = gq;> >while> (!g.empty()) {> >cout <<>' '> << g.top();> >g.pop();> >}> >cout <<>'
'>;> }> // Driver Code> int> main()> {> >priority_queue<>int>>gquiz;> >// used in inserting the element> >gquiz.push(10);> >gquiz.push(30);> >gquiz.push(20);> >gquiz.push(5);> >gquiz.push(1);> >cout <<>'The priority queue gquiz is : '>;> > >// used for highlighting the element> >showpq(gquiz);> >// used for identifying the size> >// of the priority queue> >cout <<>'
gquiz.size() : '> <<> >gquiz.size();> >// used for telling the top element> >// in priority queue> >cout <<>'
gquiz.top() : '> <<> >gquiz.top();> >// used for popping the element> >// from a priority queue> >cout <<>'
gquiz.pop() : '>;> >gquiz.pop();> >showpq(gquiz);> >return> 0;> }> |
>
>Produzione
The priority queue gquiz is : 30 20 10 5 1 gquiz.size() : 5 gquiz.top() : 30 gquiz.pop() : 20 10 5 1>
Fare riferimento all'estremità per l'analisi della complessità.
Nota : Sopra è mostrato uno dei metodi di inizializzazione della coda con priorità. Per saperne di più sull'inizializzazione efficiente della coda di priorità, fare clic qui.
2. Per accedere all'elemento principale della coda prioritaria
È possibile accedere all'elemento superiore della coda prioritaria utilizzando il file superiore() metodo.
C++
le migliori auto del mondo
// C++ program to access the top> // element of priority queue> #include> #include> using> namespace> std;> // Driver code> int> main()> {> >// create a priority queue of int> >priority_queue<>int>>numeri;> >// add items to priority_queue> >numbers.push(1);> >numbers.push(20);> >numbers.push(7);> >// get the element at the top> >cout <<>'Top element: '> <<> >numbers.top();> >return> 0;> }> |
>
>Produzione
Top element: 20>
Fare riferimento all'estremità per l'analisi della complessità.
Nota: Possiamo accedere solo all'elemento in alto nella coda di priorità.
3. Per verificare se la coda prioritaria è vuota o meno:
Usiamo il metodo empty() per verificare se la priorità_queue è vuota. Questo metodo restituisce:
- True – Viene restituito quando la coda con priorità è vuota ed è rappresentato da 1 False – Viene prodotto quando la coda con priorità non è vuota o False ed è caratterizzato da 0
Esempio:
C++
// C++ program to demonstrate> // Implementation of empty() function> #include> #include> using> namespace> std;> // Driver code> int> main()> {> >priority_queue<>int>>pqueueGFG;> >pqueueGFG.push(1);> > >// Priority Queue becomes 1> >// check if it is empty or not> >if> (pqueueGFG.empty())> >{> >cout <<>'Empty or true'>;> >}> >else> >{> >cout <<>'Contains element or False'>;> >}> >return> 0;> }> |
>
>Produzione
Contains element or False>
Fare riferimento all'estremità per l'analisi della complessità.
4. Per ottenere/controllare la dimensione della coda prioritaria
Determina la dimensione di una coda con priorità. In termini semplici, il misurare() viene utilizzato per ottenere il numero di elementi presenti nel file Coda prioritaria .
Di seguito è riportato il programma C++ per verificare la dimensione della coda di priorità:
C++
// C++ program to demonstrate the> // size() method of priority queue> #include> #include> using> namespace> std;> // Driver code> int> main()> {> >// create a priority queue of string> >priority_queue pqueue;> >// add items to priority_queue> >pqueue.push(>'Geeks'>);> >pqueue.push(>'for'>);> >pqueue.push(>'Geeks'>);> >pqueue.push(>'C++'>);> >// get the size of queue> >int> size = pqueue.size();> >cout <<>'Size of the queue: '> << size;> >return> 0;> }> |
>
>Produzione
Size of the queue: 4>
Fare riferimento all'estremità per l'analisi della complessità.
5. Per scambiare il contenuto di una coda prioritaria con un'altra di tipo simile
Scambio() La funzione viene utilizzata per scambiare il contenuto di una coda con priorità con un'altra coda con priorità dello stesso tipo e di dimensioni uguali o diverse.
Di seguito è riportato il programma C++ per scambiare il contenuto di una coda con priorità con un'altra di tipo simile:
C++
// CPP program to illustrate> // Implementation of swap() function> #include> using> namespace> std;> // Print elements of priority queue> void> print(priority_queue<>int>>pq)> {> >while> (!pq.empty()) {> >cout << pq.top() <<>' '>;> >pq.pop();> >}> >cout << endl;> }> int> main()> {> >// priority_queue container declaration> >priority_queue<>int>>pq1;> >priority_queue<>int>>pq2;> >// pushing elements into the 1st priority queue> >pq1.push(1);> >pq1.push(2);> >pq1.push(3);> >pq1.push(4);> >// pushing elements into the 2nd priority queue> >pq2.push(3);> >pq2.push(5);> >pq2.push(7);> >pq2.push(9);> >cout <<>'Before swapping:-'> << endl;> >cout <<>'Priority Queue 1 = '>;> >print(pq1);> >cout <<>'Priority Queue 2 = '>;> >print(pq2);> >// using swap() function to swap elements of priority> >// queues> >pq1.swap(pq2);> >cout << endl <<>'After swapping:-'> << endl;> >cout <<>'Priority Queue 1 = '>;> >print(pq1);> >cout <<>'Priority Queue 2 = '>;> >print(pq2);> >return> 0;> }> // This code is contributed by Susobhan Akhuli> |
>
>Produzione
Before swapping:- Priority Queue 1 = 4 3 2 1 Priority Queue 2 = 9 7 5 3 After swapping:- Priority Queue 1 = 9 7 5 3 Priority Queue 2 = 4 3 2 1>
Fare riferimento all'estremità per l'analisi della complessità.
6. Per inserire un nuovo elemento nel contenitore della coda con priorità
Posiziona() viene utilizzata per inserire un nuovo elemento nel contenitore della coda di priorità, il nuovo elemento viene aggiunto alla coda di priorità in base alla sua priorità. È simile all'operazione push. La differenza è che l'operazione emplace() salva una copia non necessaria dell'oggetto.
Di seguito è riportato il programma C++ per inserire un nuovo elemento nel contenitore della coda con priorità:
C++
// CPP program to illustrate> // Implementation of emplace() function> #include> using> namespace> std;> int> main()> {> >priority_queue<>int>>pq;> >pq.emplace(1);> >pq.emplace(2);> >pq.emplace(3);> >pq.emplace(4);> >pq.emplace(5);> >pq.emplace(6);> >// Priority queue becomes 1, 2, 3, 4, 5, 6> >// Printing the priority queue> >cout <<>'Priority Queue = '>;> >while> (!pq.empty()) {> >cout << pq.top() <<>' '>;> >pq.pop();> >}> >return> 0;> }> // This code is contributed by Susobhan Akhuli> |
>
>Produzione
Priority Queue = 6 5 4 3 2 1>
Fare riferimento all'estremità per l'analisi della complessità.
7. Per rappresentare il tipo di oggetto memorizzato come elemento in una priorità_queue
Il metodo priorità_queue :: value_type è una funzione incorporata in C++ STL che rappresenta il tipo di oggetto archiviato come elemento in una priorità_queue. Funziona come sinonimo del parametro template.
Sintassi:
priority_queue::value_type variable_name>
Di seguito è riportato il programma C++ per rappresentare il tipo di oggetto memorizzato come elemento in una priorità_queue:
C++
ciclo for in bash
// C++ program to illustrate the> // priority_queue :: value_type function> #include> using> namespace> std;> // Driver code> int> main()> {> >// declare integer value_type for priority queue> >priority_queue<>int>>::tipo_valore AnInt;> >// declare string value_type for priority queue> >priority_queue::value_type AString;> >// Declares priority_queues> >priority_queue<>int>>q1;> >priority_queue q2;> >// Here AnInt acts as a variable of int data type> >AnInt = 20;> >cout <<>'The value_type is AnInt = '> << AnInt << endl;> >q1.push(AnInt);> >AnInt = 30;> >q1.push(AnInt);> >cout <<>'Top element of the integer priority_queue is: '> ><< q1.top() << endl;> >// here AString acts as a variable of string data type> >AString =>'geek'>;> >cout << endl> ><<>'The value_type is AString = '> << AString> ><< endl;> >q2.push(AString);> >AString =>'for'>;> >q2.push(AString);> >AString =>'geeks'>;> >q2.push(AString);> >cout <<>'Top element of the string priority_queue is: '> ><< q2.top() << endl;> >return> 0;> }> // This code is contributed by Susobhan Akhuli> |
>
>Produzione
The value_type is AnInt = 20 Top element of the integer priority_queue is: 30 The value_type is AString = geek Top element of the string priority_queue is: geeks>
Fare riferimento all'estremità per l'analisi della complessità.
Complessità di tutte le operazioni:
| Metodi | Complessità temporale | Spazio ausiliario |
|---|---|---|
| priorità_coda::vuoto() | O(1) | O(1) |
| priorità_queue::dimensione() | O(1) | O(1) |
| priorità_queue::top() | O(1) | O(1) |
| priorità_queue::push() | O(logN) | O(1) |
| priorità_queue::pop() | O(logN) | O(1) |
| priorità_queue::swap() | O(1) | SU) |
| priorità_queue::emplace() | O(logN) | O(1) |
| priorità_coda tipo_valore | O(1) | O(1) |