EN C++ prioritetskø er en type containeradapter, specifikt designet sådan, at det første element i køen enten er det største eller det mindste af alle elementer i køen, og elementerne er i ikke-stigende eller ikke-faldende rækkefølge (derfor kan vi se, at hver element i køen har en prioritet {fast rækkefølge}).
I C++ STL er det øverste element altid det største som standard. Vi kan også ændre det til det mindste element øverst. Prioritetskøer er bygget på toppen af den maksimale heap og bruger et array eller vektor som en intern struktur. Enkelt sagt, STL Priority Queue er implementeringen af 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;> }> |
>
>Produktion
Array: 10 2 4 8 6 9 Priority Queue: 10 9 8 6 4 2>
Max Heap Priority Queue (standardskema)
Hvordan opretter man en min heap til prioritetskøen?
Som vi så tidligere, er en prioritetskø implementeret som max heap som standard i C++, men den giver os også en mulighed for at ændre den til min heap ved at sende en anden parameter, mens der oprettes en prioritetskø.
Syntaks:
priority_queue gq;>
hvor,
- 'int' er den type elementer, du vil gemme i prioritetskøen. I dette tilfælde er det et heltal. Du kan erstatte int med enhver anden datatype, du har brug for. 'vektor' er den type intern beholder, der bruges til at opbevare disse elementer. std::prioritetskø er ikke en container i sig selv, men en containeradopter. Det pakker andre beholdere ind. I dette eksempel bruger vi en vektor , men du kan vælge en anden beholder, der understøtter front(), push_back() og pop_back() metoder.
- ' større ' er en brugerdefineret sammenligningsfunktion. Dette bestemmer, hvordan elementerne er ordnet i prioritetskøen. I dette specifikke eksempel opsætter større en min-bunke . Det betyder, at det mindste element vil være øverst i køen.
I tilfælde af max heap behøvede vi ikke at angive dem, da standardværdierne for disse allerede er egnede til max heap.
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 |
>
>Produktion
Array: 10 2 4 8 6 9 Priority Queue : 2 4 6 8 9 10>
Min. Heap Priority Queue
Bemærk: Ovenstående syntaks kan være svær at huske, så i tilfælde af numeriske værdier kan vi gange værdierne med -1 og bruge max heap for at få effekten af min heap. Ikke kun, at vi kan bruge tilpasset sorteringsmetode ved at erstatte større med tilpasset komparatorfunktion.
Metoder til prioriteret kø
Følgende liste over alle metoderne i std::priority_queue class:
| Metode | Definition |
|---|---|
| priority_queue::empty() | Returnerer om køen er tom. |
| priority_queue::size() | Returnerer størrelsen på køen. |
| priority_queue::top() | Returnerer en reference til det øverste element i køen. |
| priority_queue::push() | Tilføjer elementet 'g' i slutningen af køen. |
| priority_queue::pop() | Sletter det første element i køen. |
| priority_queue::swap() | Bruges til at bytte indholdet af to køer, forudsat at køerne skal være af samme type, selvom størrelserne kan variere. |
| priority_queue::emplace() | Bruges til at indsætte et nyt element i prioritetskøbeholderen. |
| priority_queue value_type | Repræsenterer den type objekt, der er gemt som et element i en priority_queue. Det fungerer som et synonym for skabelonparameteren. |
Operationer på Priority Queue i C++
1. Indsættelse og fjernelse af elementer i en prioriteret kø
Det skubbe() metode bruges til at indsætte et element i prioritetskøen. For at fjerne et element fra prioritetskøen pop() metoden bruges, fordi dette fjerner elementet med den højeste prioritet.
Nedenfor er C++-programmet til forskellige funktioner i prioritetskøen:
C++
forskudt højde
// 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;> }> |
>
>Produktion
The priority queue gquiz is : 30 20 10 5 1 gquiz.size() : 5 gquiz.top() : 30 gquiz.pop() : 20 10 5 1>
Se slutningen for kompleksitetsanalyse.
Bemærk : Ovenfor er vist en af metoderne til initialisering af prioritetskø. For at vide mere om effektiv initialisering af prioritetskø, klik her.
2. For at få adgang til det øverste element i prioritetskøen
Det øverste element i Prioritetskøen kunne tilgås ved hjælp af top() 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>>tal;> >// 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;> }> |
>
b plus træ
>Produktion
Top element: 20>
Se slutningen for kompleksitetsanalyse.
Bemærk: Vi kan kun få adgang til det øverste element i prioritetskøen.
3. For at kontrollere, om prioritetskøen er tom eller ej:
Vi bruger metoden empty() til at kontrollere, om priority_queue er tom. Denne metode returnerer:
- Sand – Den returneres, når prioritetskøen er tom og er repræsenteret af 1 Falsk – Den produceres, når prioritetskøen ikke er tom eller Falsk og er karakteriseret 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;> }> |
>
>Produktion
Contains element or False>
Se slutningen for kompleksitetsanalyse.
4. For at få/tjekke størrelsen af prioritetskøen
Det bestemmer størrelsen af en prioriteret kø. Enkelt sagt størrelse() metode bruges til at få antallet af elementer til stede i Prioritetskø .
Nedenfor er C++-programmet til at kontrollere størrelsen af 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;> }> |
>
>Produktion
Size of the queue: 4>
Se slutningen for kompleksitetsanalyse.
5. At bytte indhold af en prioriteret kø med en anden af lignende type
Bytte rundt() funktion bruges til at bytte indholdet af en prioritetskø med en anden prioritetskø af samme type og samme eller forskellig størrelse.
Nedenfor er C++-programmet til at udskifte indholdet af en prioriteret kø med en anden af 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> |
>
>Produktion
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 slutningen for kompleksitetsanalyse.
6. At indsætte et nyt element i prioritetskøbeholderen
Emplace() funktionen bruges til at indsætte et nyt element i prioritetskøbeholderen, tilføjes det nye element til prioritetskøen i henhold til dets prioritet. Det ligner push-operation. Forskellen er, at emplace()-operationen gemmer unødvendig kopi af objektet.
Nedenfor er C++-programmet til at indsætte et nyt 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> |
>
>Produktion
Priority Queue = 6 5 4 3 2 1>
Se slutningen for kompleksitetsanalyse.
7. At repræsentere den type objekt, der er gemt som et element i en priority_queue
Priority_queue :: value_type metoden er en indbygget funktion i C++ STL, som repræsenterer den type objekt, der er gemt som et element i en priority_queue. Det fungerer som et synonym for skabelonparameteren.
Syntaks:
priority_queue::value_type variable_name>
Nedenfor er C++-programmet til at repræsentere den type objekt, der er gemt som et element i en priority_queue:
C++
kamelhylster 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>>::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> |
>
>Produktion
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 slutningen for kompleksitetsanalyse.
Alle operationers kompleksitet:
| Metoder | Tidskompleksitet | Hjælpeplads |
|---|---|---|
| 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) |
| priority_queue value_type | O(1) | O(1) |