A Cua de prioritats C++ és un tipus d'adaptador de contenidors, dissenyat específicament de manera que el primer element de la cua sigui el més gran o el més petit de tots els elements de la cua, i els elements estiguin en ordre no creixent o no decreixent (per tant podem veure que cada element de la cua té una prioritat {ordre fix}).
En C++ STL, l'element superior sempre és el més gran per defecte. També podem canviar-lo a l'element més petit de la part superior. Les cues de prioritat es construeixen a la part superior de la pila màxima i utilitzen una matriu o un vector com a estructura interna. En termes senzills, Cua de prioritat STL és la implementació de 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;> }> |
>
>Sortida
Array: 10 2 4 8 6 9 Priority Queue: 10 9 8 6 4 2>
Cua de prioritat màxima de la pila (esquema predeterminat)
Com crear un munt mínim per a la cua de prioritats?
Com hem vist anteriorment, una cua de prioritat s'implementa com a munt màxim de manera predeterminada en C++, però també ens ofereix una opció per canviar-la a munt mínim passant un altre paràmetre mentre es crea una cua de prioritat.
Sintaxi:
priority_queue gq;>
on,
- 'int' és el tipus d'elements que voleu emmagatzemar a la cua de prioritats. En aquest cas, és un nombre enter. Podeu substituir int amb qualsevol altre tipus de dades que necessiteu. 'vector' és el tipus de contenidor intern utilitzat per emmagatzemar aquests elements. std::priority_queue no és un contenidor en si mateix sinó un adoptador de contenidors. Embolcalla altres contenidors. En aquest exemple, estem utilitzant a vector , però podeu triar un contenidor diferent que admeti els mètodes front(), push_back() i pop_back().
- ‘ més gran 'és una funció de comparació personalitzada. Això determina com s'ordenen els elements dins de la cua de prioritats. En aquest exemple específic, configuracions més grans a min-munt . Vol dir que l'element més petit estarà a la part superior de la cua.
En el cas de l'emmagatzematge màxim, no hem hagut d'especificar-los, ja que els valors per defecte ja són adequats per a l'emmagatzematge màxim.
Exemple:
C++
// C++ program to demonstrate> // min heap for priority queue> #include> #include> using> namespace> std;> void> showpq(> >priority_queue<>int>, vector<>int>>, més gran<>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 |
>
>Sortida
Array: 10 2 4 8 6 9 Priority Queue : 2 4 6 8 9 10>
Cua de prioritat mínima d'heap
Nota: La sintaxi anterior pot ser difícil de recordar, de manera que en cas de valors numèrics, podem multiplicar els valors amb -1 i utilitzar l'emmagatzematge màxim per obtenir l'efecte de l'emmagatzematge min. No només podem utilitzar el mètode d'ordenació personalitzat mitjançant la substitució més gran amb funció de comparació personalitzada.
Mètodes de cua de prioritat
La llista següent de tots els mètodes de la classe std::priority_queue:
| Mètode | Definició |
|---|---|
| priority_queue::empty() | Retorna si la cua està buida. |
| priority_queue::size() | Retorna la mida de la cua. |
| priority_queue::top() | Retorna una referència a l'element superior de la cua. |
| priority_queue::push() | Afegeix l'element 'g' al final de la cua. |
| priority_queue::pop() | Esborra el primer element de la cua. |
| priority_queue::swap() | S'utilitza per intercanviar el contingut de dues cues sempre que les cues hagin de ser del mateix tipus, encara que les mides poden ser diferents. |
| priority_queue::emplace() | S'utilitza per inserir un element nou al contenidor de la cua de prioritat. |
| priority_queue value_type | Representa el tipus d'objecte emmagatzemat com a element en una priority_queue. Actua com a sinònim del paràmetre de plantilla. |
Operacions a la cua de prioritats en C++
1. Inserció i eliminació d'elements d'una cua de prioritat
El empènyer () s'utilitza per inserir un element a la cua de prioritats. Per eliminar un element de la cua de prioritats el pop() s'utilitza perquè això elimina l'element amb la prioritat més alta.
A continuació es mostra el programa C++ per a diverses funcions de la cua de prioritats:
C++
// 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;> }> |
>
>Sortida
The priority queue gquiz is : 30 20 10 5 1 gquiz.size() : 5 gquiz.top() : 30 gquiz.pop() : 20 10 5 1>
Consulteu el final per a l'anàlisi de complexitat.
Nota : A dalt es mostra un dels mètodes d'inicialització de la cua de prioritat. Per obtenir més informació sobre la inicialització eficient de la cua de prioritats, feu clic aquí.
2. Per accedir a l'element superior de la cua de prioritats
Es pot accedir a l'element superior de la cua de prioritats mitjançant l' superior() mètode.
C++
// 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>>nombres;> >// 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;> }> |
>
>Sortida
Top element: 20>
Consulteu el final per a l'anàlisi de la complexitat.
Nota: Només podem accedir a l'element superior de la cua de prioritats.
3. Per comprovar si la cua de prioritats està buida o no:
Utilitzem el mètode empty() per comprovar si priority_queue està buida. Aquest mètode retorna:
- Vertader: es retorna quan la cua de prioritat està buida i es representa amb 1 Fals: es produeix quan la cua de prioritat no està buida o Fals i es caracteritza per 0
Exemple:
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;> }> |
>
>Sortida
Contains element or False>
Consulteu el final per a l'anàlisi de complexitat.
4. Per obtenir/comprovar la mida de la cua de prioritats
Determina la mida d'una cua de prioritat. En termes senzills, el mida () s'utilitza el mètode per obtenir el nombre d'elements presents en el Cua de prioritats .
A continuació es mostra el programa C++ per comprovar la mida de la cua de prioritats:
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;> }> |
>
>Sortida
Size of the queue: 4>
Consulteu el final per a l'anàlisi de complexitat.
5. Per intercanviar el contingut d'una cua de prioritat per una altra de tipus semblant
Canvi () La funció s'utilitza per intercanviar el contingut d'una cua de prioritat amb una altra cua de prioritat del mateix tipus i de la mateixa o diferent mida.
A continuació es mostra el programa C++ per intercanviar el contingut d'una cua de prioritat amb una altra de tipus similar:
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> |
>
>Sortida
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>
Consulteu el final per a l'anàlisi de complexitat.
6. Col·locar un element nou al contenidor de la cua de prioritat
Emplaceu() La funció s'utilitza per inserir un element nou al contenidor de la cua de prioritat, l'element nou s'afegeix a la cua de prioritat segons la seva prioritat. És similar a l'operació push. La diferència és que l'operació emplace() desa una còpia innecessària de l'objecte.
A continuació es mostra el programa C++ per col·locar un element nou al contenidor de la cua de prioritats:
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> |
corda de llargada
>
>Sortida
Priority Queue = 6 5 4 3 2 1>
Consulteu el final per a l'anàlisi de complexitat.
7. Representar el tipus d'objecte emmagatzemat com a element en una priority_queue
El mètode priority_queue :: value_type és una funció integrada a C++ STL que representa el tipus d'objecte emmagatzemat com a element en una priority_queue. Actua com a sinònim del paràmetre de plantilla.
Sintaxi:
priority_queue::value_type variable_name>
A continuació es mostra el programa C++ per representar el tipus d'objecte emmagatzemat com a element en una priority_queue:
C++
// 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>>::value_type 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> |
>
>Sortida
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>
Consulteu el final per a l'anàlisi de complexitat.
Complexitats de totes les operacions:
| Mètodes | Complexitat temporal | Espai Auxiliar |
|---|---|---|
| priority_queue::empty() | O(1) | O(1) |
| priority_queue::size() | O(1) | O(1) |
| priority_queue::top() | O(1) | O(1) |
| priority_queue::push() | O(logN) | O(1) |
| priority_queue::pop() | O(logN) | O(1) |
| priority_queue::swap() | O(1) | O(N) |
| priority_queue::emplace() | O(logN) | O(1) |
| priority_queue value_type | O(1) | O(1) |