EN C++ prioritetskø er en type containeradapter , spesielt utformet slik at det første elementet i køen enten er det største eller det minste av alle elementene i køen, og elementene er i ikke-økende eller ikke-minkende rekkefølge (derav kan vi se at hver element i køen har en prioritet {fast rekkefølge}).
I C++ STL er toppelementet alltid det største som standard. Vi kan også endre det til det minste elementet øverst. Prioritetskøer bygges på toppen av maks-heapen og bruker en matrise eller vektor som en intern struktur. For å si det enkelt, STL Priority Queue er implementeringen av 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;> }> |
>
>Produksjon
Array: 10 2 4 8 6 9 Priority Queue: 10 9 8 6 4 2>
Max Heap Priority Queue (standardoppsett)
Hvordan lage en min haug for prioritetskøen?
Som vi så tidligere, er en prioritetskø implementert som maks haug som standard i C++, men den gir oss også en mulighet til å endre den til min haug ved å sende en annen parameter mens du oppretter en prioritetskø.
Syntaks:
priority_queue gq;>
hvor,
- 'int' er typen elementer du vil lagre i prioritetskøen. I dette tilfellet er det et heltall. Du kan erstatte int med alle andre datatyper du trenger. 'vektor' er typen intern beholder som brukes til å lagre disse elementene. std::prioritetskø er ikke en container i seg selv, men en containeradopter. Den pakker inn andre beholdere. I dette eksemplet bruker vi en vektor , men du kan velge en annen beholder som støtter front(), push_back() og pop_back() metoder.
- ' større ' er en tilpasset sammenligningsfunksjon. Dette bestemmer hvordan elementene er sortert i prioritetskøen. I dette spesifikke eksemplet setter større opp en min-haug . Det betyr at det minste elementet vil stå øverst i køen.
Når det gjelder maks haug, trengte vi ikke å spesifisere dem, da standardverdiene for disse allerede er egnet for maks haug.
Eksempel:
C++
// C++ program to demonstrate> // min heap for priority queue> #include> #include> using> namespace> std;> void> showpq(> >priority_queue<>int>, vector<>int>>, større<>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 |
>
>Produksjon
Array: 10 2 4 8 6 9 Priority Queue : 2 4 6 8 9 10>
Min haugprioritetskø
Merk: Syntaksen ovenfor kan være vanskelig å huske, så i tilfelle av numeriske verdier, kan vi multiplisere verdiene med -1 og bruke max heap for å få effekten av min heap. Ikke bare det at vi kan bruke tilpasset sorteringsmetode ved å erstatte større med tilpasset komparatorfunksjon.
Metoder for prioritert kø
Følgende liste over alle metodene for std::priority_queue class:
| Metode | Definisjon |
|---|---|
| priority_queue::empty() | Returnerer om køen er tom. |
| priority_queue::size() | Returnerer størrelsen på køen. |
| priority_queue::top() | Returnerer en referanse til det øverste elementet i køen. |
| priority_queue::push() | Legger til elementet 'g' på slutten av køen. |
| priority_queue::pop() | Sletter det første elementet i køen. |
| priority_queue::swap() | Brukes til å bytte innholdet i to køer forutsatt at køene må være av samme type, selv om størrelsene kan variere. |
| priority_queue::emplace() | Brukes til å sette inn et nytt element i prioritetskøbeholderen. |
| prioritetskø verditype | Representerer typen objekt som er lagret som et element i en priority_queue. Den fungerer som et synonym for malparameteren. |
Operasjoner på Priority Queue i C++
1. Sette inn og fjerne elementer i en prioritert kø
De trykk() metoden brukes til å sette inn et element i prioritetskøen. For å fjerne et element fra prioritetskøen pop() metoden brukes fordi dette fjerner elementet med høyest prioritet.
Nedenfor er C++-programmet for ulike funksjoner i prioritetskøen:
C++
forskjøvet høyde
// 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;> }> |
>
>Produksjon
The priority queue gquiz is : 30 20 10 5 1 gquiz.size() : 5 gquiz.top() : 30 gquiz.pop() : 20 10 5 1>
Se slutten for kompleksitetsanalyse.
Merk : Over vist er en av metodene for initialisering av prioritert kø. For å vite mer om effektiv initialisering av prioritetskø, klikk her.
2. For å få tilgang til det øverste elementet i prioritert kø
Det øverste elementet i Priority Queue kunne nås ved å bruke topp() metode.
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>>tall;> >// 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;> }> |
>
sql konkat
>Produksjon
Top element: 20>
Se slutten for kompleksitetsanalyse.
Merk: Vi har kun tilgang til det øverste elementet i prioritetskøen.
3. For å sjekke om prioritetskøen er tom eller ikke:
Vi bruker metoden empty() for å sjekke om priority_queue er tom. Denne metoden returnerer:
- True – Den returneres når prioritetskøen er tom og er representert med 1 False – Den produseres når prioritetskøen ikke er tom eller False og er karakterisert ved 0
Eksempel:
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;> }> |
>
>Produksjon
Contains element or False>
Se slutten for kompleksitetsanalyse.
4. For å få/sjekke størrelsen på prioritert kø
Den bestemmer størrelsen på en prioritert kø. Enkelt sagt størrelse() metoden brukes for å få antall elementer som er tilstede i Prioritetskø .
Nedenfor er C++-programmet for å sjekke størrelsen på prioritetskøen:
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;> }> |
>
>Produksjon
Size of the queue: 4>
Se slutten for kompleksitetsanalyse.
5. For å bytte innhold i en prioritert kø med en annen av lignende type
Bytte() funksjonen brukes til å bytte innholdet i en prioritetskø med en annen prioritetskø av samme type og samme eller forskjellig størrelse.
Nedenfor er C++-programmet for å bytte innhold i en prioritert kø med en annen av lignende 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> |
>
>Produksjon
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>
Se slutten for kompleksitetsanalyse.
6. For å legge inn et nytt element i prioritetskøbeholderen
Emplace() funksjonen brukes til å sette inn et nytt element i prioritetskøbeholderen, blir det nye elementet lagt til prioritetskøen i henhold til dets prioritet. Det ligner på push-operasjon. Forskjellen er at emplace()-operasjonen lagrer unødvendig kopi av objektet.
Nedenfor er C++-programmet for å plassere et nytt element i prioritetskøbeholderen:
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> |
>
>Produksjon
Priority Queue = 6 5 4 3 2 1>
Se slutten for kompleksitetsanalyse.
7. Å representere typen objekt som er lagret som et element i en priority_queue
Priority_queue :: value_type-metoden er en innebygd funksjon i C++ STL som representerer typen objekt som er lagret som et element i en priority_queue. Den fungerer som et synonym for malparameteren.
Syntaks:
priority_queue::value_type variable_name>
Nedenfor er C++-programmet for å representere typen objekt som er lagret som et element i en priority_queue:
C++
kamelvesken python
// 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>>::verditype 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> |
>
>Produksjon
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>
Se slutten for kompleksitetsanalyse.
Kompleksiteten til alle operasjonene:
| Metoder | Tidskompleksitet | Auxiliary Space |
|---|---|---|
| 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) | PÅ) |
| priority_queue::emplace() | O(logN) | O(1) |
| prioritetskø verditype | O(1) | O(1) |