A C++ prioritetskö är en typ av containeradapter, speciellt utformad så att det första elementet i kön är antingen det största eller det minsta av alla element i kön, och elementen är i icke-ökande eller icke-minskande ordning (därav vi kan se att varje element i kön har en prioritet {fast ordning}).
I C++ STL är det översta elementet alltid störst som standard. Vi kan också ändra det till det minsta elementet överst. Prioritetsköer byggs på toppen av maxhögen och använder en array eller vektor som en intern struktur. I enkla termer, STL Priority Queue är 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;> }> |
>
>Produktion
Array: 10 2 4 8 6 9 Priority Queue: 10 9 8 6 4 2>
Max Heap Priority Queue (standardschema)
Hur skapar man en min heap för prioritetskön?
Som vi såg tidigare är en prioritetskö implementerad som maxhög som standard i C++ men den ger oss också ett alternativ att ändra den till minhög genom att skicka en annan parameter samtidigt som en prioritetskö skapas.
Syntax:
priority_queue gq;>
var,
- 'int' är den typ av element du vill lagra i prioritetskön. I det här fallet är det ett heltal. Du kan byta ut int med någon annan datatyp du behöver. 'vektor' är den typ av intern behållare som används för att lagra dessa element. std::priority_queue är inte en container i sig utan en container adopter. Den slår in andra behållare. I det här exemplet använder vi en vektor , men du kan välja en annan behållare som stöder metoderna front(), push_back() och pop_back().
- ' större ' är en anpassad jämförelsefunktion. Detta bestämmer hur elementen ordnas i prioritetskön. I detta specifika exempel, större inställningar a min-hög . Det betyder att det minsta elementet kommer att stå överst i kön.
När det gäller max heap behövde vi inte ange dem eftersom standardvärdena för dessa redan är lämpliga för max heap.
Exempel:
alfabetet till nummer
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
Notera: Ovanstående syntax kan vara svår att komma ihåg, så vid numeriska värden kan vi multiplicera värdena med -1 och använda max heap för att få effekten av min heap. Inte bara det att vi kan använda anpassad sorteringsmetod genom att ersätta större med anpassad komparatorfunktion.
Metoder för prioriterad kö
Följande lista över alla metoder för std::priority_queue class:
| Metod | Definition |
|---|---|
| priority_queue::empty() | Returnerar om kön är tom. |
| priority_queue::size() | Returnerar storleken på kön. |
| priority_queue::top() | Returnerar en referens till det översta elementet i kön. |
| priority_queue::push() | Lägger till elementet 'g' i slutet av kön. |
| priority_queue::pop() | Tar bort det första elementet i kön. |
| priority_queue::swap() | Används för att byta innehåll i två köer förutsatt att köerna måste vara av samma typ, även om storlekarna kan skilja sig åt. |
| priority_queue::emplace() | Används för att infoga ett nytt element i prioritetsköbehållaren. |
| priority_queue value_type | Representerar typen av objekt som lagras som ett element i en priority_queue. Den fungerar som en synonym för mallparametern. |
Operationer på Priority Queue i C++
1. Infoga och ta bort element i en prioriterad kö
De skjuta på() metod används för att infoga ett element i prioritetskön. För att ta bort ett element från prioritetskön, pop() metod används eftersom detta tar bort elementet med högst prioritet.
Nedan är C++-programmet för olika funktioner i prioritetskön:
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;> }> |
>
>Produktion
The priority queue gquiz is : 30 20 10 5 1 gquiz.size() : 5 gquiz.top() : 30 gquiz.pop() : 20 10 5 1>
Se slutet för komplexitetsanalys.
Notera : Ovan visas en av metoderna för initiering av prioriterad kö. För att veta mer om effektiv initiering av prioritetskö, klicka här.
2. För att komma åt det översta elementet i prioritetskön
Det översta elementet i Priority Queue kunde nås med hjälp av topp() metod.
C++
sträng java array
// 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>>siffror;> >// 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;> }> |
>
>Produktion
Top element: 20>
Se slutet för komplexitetsanalys.
Notera: Vi kan bara komma åt det översta elementet i prioritetskön.
3. Så här kontrollerar du om prioritetskön är tom eller inte:
Vi använder metoden empty() för att kontrollera om priority_queue är tom. Denna metod returnerar:
- True – Den returneras när prioritetskön är tom och representeras av 1 False – Den produceras när prioritetskön inte är tom eller False och kännetecknas av 0
Exempel:
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 slutet för komplexitetsanalys.
4. För att få/kontrollera storleken på prioritetskön
Det bestämmer storleken på en prioriterad kö. Enkelt uttryckt storlek() metod används för att få antalet element som finns i Prioriterad kö .
avgränsare java
Nedan är C++-programmet för att kontrollera storleken på prioritetskön:
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 slutet för komplexitetsanalys.
5. Att byta innehåll i en prioriterad kö med en annan av liknande typ
Byta() funktionen används för att byta innehållet i en prioritetskö med en annan prioritetskö av samma typ och samma eller olika storlek.
Nedan är C++-programmet för att byta innehåll i en prioriterad kö med en annan av liknande typ:
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> |
vem är freddie mercury
>
>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 slutet för komplexitetsanalys.
6. Att placera ett nytt element i prioritetsköbehållaren
Emplace() funktionen används för att infoga ett nytt element i prioritetsköbehållaren, det nya elementet läggs till i prioritetskön enligt dess prioritet. Det liknar push-operation. Skillnaden är att emplace()-operationen sparar onödig kopia av objektet.
Nedan är C++-programmet för att placera ett nytt element i prioritetsköbehållaren:
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 slutet för komplexitetsanalys.
7. För att representera typen av objekt som lagras som ett element i en priority_queue
Priority_queue :: value_type-metoden är en inbyggd funktion i C++ STL som representerar den typ av objekt som lagras som ett element i en priority_queue. Den fungerar som en synonym för mallparametern.
Syntax:
priority_queue::value_type variable_name>
Nedan är programmet C++ för att representera den typ av objekt som lagras som ett element i en 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> |
>
>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 slutet för komplexitetsanalys.
Komplexiteter för alla operationer:
| Metoder | Tidskomplexitet | Hjälputrymme |
|---|---|---|
| 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) ankita lokhande ålder | O(1) |