A C++ prioriteitswachtrij is een type containeradapter, speciaal zo ontworpen dat het eerste element van de wachtrij het grootste of het kleinste van alle elementen in de wachtrij is, en dat de elementen in niet-oplopende of niet-afnemende volgorde staan (daarom kunnen we zien dat elk element van de wachtrij heeft een prioriteit {vaste volgorde}).
In C++ STL is het bovenste element standaard altijd het grootste. We kunnen het ook veranderen naar het kleinste element bovenaan. Prioriteitswachtrijen worden bovenop de maximale heap gebouwd en gebruiken een array of vector als interne structuur. In simpele termen, STL-prioriteitwachtrij is de implementatie van 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;> }> |
>
>Uitvoer
Array: 10 2 4 8 6 9 Priority Queue: 10 9 8 6 4 2>
Max Heap Priority Queue (standaardschema)
Hoe maak ik een min-heap voor de prioriteitswachtrij?
Zoals we eerder zagen, wordt een prioriteitswachtrij standaard geïmplementeerd als max heap in C++, maar het biedt ons ook een optie om deze te wijzigen in min heap door een andere parameter door te geven terwijl een prioriteitswachtrij wordt gemaakt.
Syntaxis:
priority_queue gq;>
waar,
- ‘int’ is het type elementen dat u in de prioriteitswachtrij wilt opslaan. In dit geval is het een geheel getal. Je kunt vervangen int met elk ander gegevenstype dat u nodig heeft. ‘vector’ is het type interne container dat wordt gebruikt om deze elementen op te slaan. std::priority_queue is op zichzelf geen container, maar een containeradopter. Het wikkelt andere containers. In dit voorbeeld gebruiken we a vector , maar u kunt een andere container kiezen die de methoden front(), push_back() en pop_back() ondersteunt.
- ' groter ‘ is een aangepaste vergelijkingsfunctie. Dit bepaalt hoe de elementen binnen de prioriteitswachtrij worden geordend. In dit specifieke voorbeeld stelt groter a in min-hoop . Het betekent dat het kleinste element bovenaan de wachtrij staat.
In het geval van max heap hoefden we deze niet op te geven, omdat de standaardwaarden hiervoor al geschikt zijn voor max heap.
Voorbeeld:
C++
// C++ program to demonstrate> // min heap for priority queue> #include> #include> using> namespace> std;> void> showpq(> >priority_queue<>int>, vector<>int>>, groter<>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 |
>
>Uitvoer
Array: 10 2 4 8 6 9 Priority Queue : 2 4 6 8 9 10>
Prioriteitswachtrij voor minimale hoop
tekenreeksdatum converteren
Opmerking: De bovenstaande syntaxis is misschien moeilijk te onthouden, dus in het geval van numerieke waarden kunnen we de waarden vermenigvuldigen met -1 en max heap gebruiken om het effect van min heap te krijgen. Niet alleen dat we een aangepaste sorteermethode kunnen gebruiken door te vervangen groter met aangepaste vergelijkingsfunctie.
Methoden voor prioriteitswachtrij
De volgende lijst met alle methoden van de klasse std::priority_queue:
| Methode | Definitie |
|---|---|
| prioriteitswachtrij::empty() | Geeft terug of de wachtrij leeg is. |
| prioriteitswachtrij::size() | Retourneert de grootte van de wachtrij. |
| prioriteitswachtrij::top() | Retourneert een verwijzing naar het bovenste element van de wachtrij. |
| prioriteitswachtrij::push() | Voegt het element ‘g’ toe aan het einde van de wachtrij. |
| prioriteitswachtrij::pop() | Verwijdert het eerste element van de wachtrij. |
| prioriteitswachtrij::swap() | Wordt gebruikt om de inhoud van twee wachtrijen om te wisselen, op voorwaarde dat de wachtrijen van hetzelfde type moeten zijn, hoewel de grootte kan verschillen. |
| prioriteitswachtrij::emplace() | Wordt gebruikt om een nieuw element in de prioriteitswachtrijcontainer in te voegen. |
| prioriteit_wachtrij waarde_type | Vertegenwoordigt het type object dat is opgeslagen als een element in een prioriteitswachtrij. Het fungeert als synoniem voor de sjabloonparameter. |
Bewerkingen op prioriteitswachtrij in C++
1. Elementen van een prioriteitswachtrij invoegen en verwijderen
De duw() methode wordt gebruikt om een element in de prioriteitswachtrij in te voegen. Om een element uit de prioriteitswachtrij te verwijderen, gebruikt u het knal() methode wordt gebruikt omdat hierdoor het element met de hoogste prioriteit wordt verwijderd.
amisha patel
Hieronder vindt u het C++-programma voor verschillende functies in de prioriteitswachtrij:
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;> }> |
>
>Uitvoer
The priority queue gquiz is : 30 20 10 5 1 gquiz.size() : 5 gquiz.top() : 30 gquiz.pop() : 20 10 5 1>
Raadpleeg het einde voor complexiteitsanalyse.
Opmerking : Hierboven ziet u een van de methoden voor initialisatie van prioriteitswachtrijen. Klik hier voor meer informatie over de efficiënte initialisatie van de prioriteitswachtrij.
2. Toegang krijgen tot het bovenste element van de prioriteitswachtrij
Het bovenste element van de Prioriteitswachtrij is toegankelijk via de bovenkant() methode.
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>>cijfers;> >// 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;> }> |
>
>Uitvoer
Top element: 20>
Raadpleeg het einde voor complexiteitsanalyse.
Opmerking: We hebben alleen toegang tot het bovenste element in de prioriteitswachtrij.
3. Controleren of de prioriteitswachtrij leeg is of niet:
We gebruiken de empty() methode om te controleren of de prioriteit_wachtrij leeg is. Deze methode retourneert:
- True – Het wordt geretourneerd als de prioriteitswachtrij leeg is en wordt weergegeven door 1 False – Het wordt geproduceerd als de prioriteitswachtrij niet leeg of False is en wordt gekenmerkt door 0
Voorbeeld:
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;> }> |
>
>Uitvoer
Contains element or False>
Raadpleeg het einde voor complexiteitsanalyse.
4. Om de grootte van de prioriteitswachtrij op te halen/controleren
Het bepaalt de grootte van een prioriteitswachtrij. In eenvoudige bewoordingen: de maat() methode wordt gebruikt om het aantal aanwezige elementen in de te verkrijgen Prioriteits-rij .
Hieronder vindt u het C++-programma om de grootte van de prioriteitswachtrij te controleren:
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;> }> |
>
>Uitvoer
scripts uitvoeren onder Linux
Size of the queue: 4>
Raadpleeg het einde voor complexiteitsanalyse.
5. Om de inhoud van een prioriteitswachtrij te verwisselen met een andere van hetzelfde type
Ruil() De functie wordt gebruikt om de inhoud van een prioriteitswachtrij te verwisselen met een andere prioriteitswachtrij van hetzelfde type en dezelfde of een andere grootte.
Hieronder staat het C++-programma om de inhoud van een prioriteitswachtrij te wisselen met een andere van hetzelfde type:
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> |
>
>Uitvoer
Linux hoe je een map hernoemt
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>
Raadpleeg het einde voor complexiteitsanalyse.
6. Om een nieuw element in de prioriteitswachtrijcontainer te plaatsen
Plaats() functie wordt gebruikt om een nieuw element in de prioriteitswachtrijcontainer in te voegen, het nieuwe element wordt toegevoegd aan de prioriteitswachtrij op basis van zijn prioriteit. Het is vergelijkbaar met push-bediening. Het verschil is dat de bewerking emplace() onnodige kopieën van het object bespaart.
Hieronder vindt u het C++-programma om een nieuw element in de prioriteitswachtrijcontainer te plaatsen:
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> |
>
>Uitvoer
Priority Queue = 6 5 4 3 2 1>
Raadpleeg het einde voor complexiteitsanalyse.
7. Om het type object weer te geven dat is opgeslagen als een element in een prioriteitswachtrij
De methode prioriteit_wachtrij :: waarde_type is een ingebouwde functie in C++ STL die het type object vertegenwoordigt dat is opgeslagen als een element in een prioriteitswachtrij. Het fungeert als synoniem voor de sjabloonparameter.
Syntaxis:
priority_queue::value_type variable_name>
Hieronder staat het C++-programma dat het type object weergeeft dat is opgeslagen als een element in een prioriteitswachtrij:
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> |
>
>
alfabet op nummerUitvoer
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>
Raadpleeg het einde voor complexiteitsanalyse.
Complexiteiten van alle operaties:
| Methoden | Tijdcomplexiteit | Hulpruimte |
|---|---|---|
| prioriteitswachtrij::empty() | O(1) | O(1) |
| prioriteitswachtrij::size() | O(1) | O(1) |
| prioriteitswachtrij::top() | O(1) | O(1) |
| prioriteitswachtrij::push() | O(logN) | O(1) |
| prioriteitswachtrij::pop() | O(logN) | O(1) |
| prioriteitswachtrij::swap() | O(1) | OP) |
| prioriteitswachtrij::emplace() | O(logN) | O(1) |
| prioriteit_wachtrij waarde_type | O(1) | O(1) |