A Prednostna čakalna vrsta C++ je vrsta adapterja vsebnika, posebej zasnovana tako, da je prvi element čakalne vrste največji ali najmanjši od vseh elementov v čakalni vrsti, elementi pa so v nenaraščajočem ali nepadajočem vrstnem redu (zato lahko vidimo, da je vsak element čakalne vrste ima prednost {fiksni vrstni red}).
V C++ STL je zgornji element privzeto vedno največji. Spremenimo ga lahko tudi na najmanjši element na vrhu. Prednostne čakalne vrste so zgrajene na vrhu največje kopice in kot notranjo strukturo uporabljajo niz ali vektor. Preprosto povedano, Prednostna čakalna vrsta STL je implementacija 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;> }> |
>
>Izhod
Array: 10 2 4 8 6 9 Priority Queue: 10 9 8 6 4 2>
Največja prednostna čakalna vrsta kopice (privzeta shema)
Kako ustvariti min kopico za prednostno čakalno vrsto?
Kot smo videli prej, je prednostna čakalna vrsta v C++ privzeto implementirana kot največja kopica, vendar nam ponuja tudi možnost, da jo spremenimo v najmanjšo kopico s posredovanjem drugega parametra med ustvarjanjem prednostne čakalne vrste.
Sintaksa:
priority_queue gq;>
kje,
- 'int' je vrsta elementov, ki jih želite shraniti v prednostno čakalno vrsto. V tem primeru je to celo število. Lahko zamenjate int s katero koli drugo vrsto podatkov, ki jo potrebujete. 'vector' je vrsta notranjega vsebnika, ki se uporablja za shranjevanje teh elementov. std::priority_queue ni vsebnik sam po sebi, ampak posvojnik vsebnika. Ovije druge posode. V tem primeru uporabljamo a vektor , vendar lahko izberete drug vsebnik, ki podpira metode front(), push_back() in pop_back().
- ' večji ' je primerjalna funkcija po meri. To določa, kako so elementi urejeni v prednostni čakalni vrsti. V tem konkretnem primeru večja nastavi a min-kup . To pomeni, da bo najmanjši element na vrhu čakalne vrste.
V primeru največjega kupa nam jih ni bilo treba določiti, saj so privzete vrednosti za te že primerne za največji kup.
primer:
C++
// C++ program to demonstrate> // min heap for priority queue> #include> #include> using> namespace> std;> void> showpq(> >priority_queue<>int>, vector<>int>>, večji<>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 |
>
>Izhod
Array: 10 2 4 8 6 9 Priority Queue : 2 4 6 8 9 10>
Najmanjša prednostna čakalna vrsta kopice
Opomba: Zgornjo sintakso si je morda težko zapomniti, zato lahko v primeru številskih vrednosti vrednosti pomnožimo z -1 in uporabimo največjo kopico, da dobimo učinek najmanjše kopice. Ne samo, da lahko uporabimo metodo razvrščanja po meri z zamenjavo večji s funkcijo primerjalnika po meri.
Metode prednostne čakalne vrste
Naslednji seznam vseh metod razreda std::priority_queue:
| Metoda | Opredelitev |
|---|---|
| priority_queue::empty() | Vrne, ali je čakalna vrsta prazna. |
| priority_queue::size() | Vrne velikost čakalne vrste. |
| priority_queue::top() | Vrne sklic na najvišji element čakalne vrste. |
| priority_queue::push() | Doda element 'g' na konec čakalne vrste. |
| priority_queue::pop() | Izbriše prvi element čakalne vrste. |
| priority_queue::swap() | Uporablja se za zamenjavo vsebine dveh čakalnih vrst, pod pogojem, da morata biti čakalni vrsti iste vrste, čeprav se velikosti lahko razlikujejo. |
| priority_queue::emplace() | Uporablja se za vstavljanje novega elementa v vsebnik prednostne čakalne vrste. |
| prednostna_čakalna_vrsta_vrsta_vrednosti | Predstavlja vrsto predmeta, shranjenega kot element v priority_queue. Deluje kot sinonim za parameter predloge. |
Operacije v prednostni čakalni vrsti v C++
1. Vstavljanje in odstranjevanje elementov prednostne čakalne vrste
The potisni() metoda se uporablja za vstavljanje elementa v prednostno čakalno vrsto. Za odstranitev elementa iz prednostne čakalne vrste pop() uporabljena metoda, ker s tem odstranimo element z najvišjo prioriteto.
Spodaj je program C++ za različne funkcije v prednostni čakalni vrsti:
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>>gkviz;> >// 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;> }> |
>
>Izhod
The priority queue gquiz is : 30 20 10 5 1 gquiz.size() : 5 gquiz.top() : 30 gquiz.pop() : 20 10 5 1>
Napotite se na konec za analizo kompleksnosti.
Opomba : Zgoraj je prikazana ena od metod inicializacije prednostne čakalne vrste. Če želite izvedeti več o učinkoviti inicializaciji prednostne čakalne vrste, kliknite tukaj.
2. Za dostop do zgornjega elementa prednostne čakalne vrste
Do zgornjega elementa prednostne čakalne vrste lahko dostopate z vrh() metoda.
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>>številke;> >// 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;> }> |
>
>Izhod
Top element: 20>
Napotite se na konec za analizo kompleksnosti.
Opomba: Dostopamo lahko samo do zgornjega elementa v prednostni čakalni vrsti.
3. Če želite preveriti, ali je prednostna čakalna vrsta prazna ali ne:
Z metodo empty() preverimo, ali je priority_queue prazna. Ta metoda vrne:
- True – Vrne se, ko je prednostna čakalna vrsta prazna in je predstavljena z 1 False – Izdela se, ko prednostna čakalna vrsta ni prazna ali False in je označena z 0
primer:
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;> }> |
>
>Izhod
Contains element or False>
Napotite se na konec za analizo kompleksnosti.
4. Za pridobitev/preverjanje velikosti prednostne čakalne vrste
Določa velikost prednostne čakalne vrste. Preprosto povedano, velikost () metoda se uporablja za pridobitev števila elementov, prisotnih v Prednostna čakalna vrsta .
Spodaj je program C++ za preverjanje velikosti prednostne čakalne vrste:
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;> }> |
>
>Izhod
Size of the queue: 4>
Napotite se na konec za analizo kompleksnosti.
5. Za zamenjavo vsebine prednostne čakalne vrste z drugo podobnega tipa
Zamenjaj() funkcija se uporablja za zamenjavo vsebine ene prednostne čakalne vrste z drugo prednostno čakalno vrsto iste vrste in enake ali drugačne velikosti.
Spodaj je program C++ za zamenjavo vsebine prednostne čakalne vrste z drugo podobne vrste:
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> |
>
>
matriko v jeziku cIzhod
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>
Napotite se na konec za analizo kompleksnosti.
6. Za vgradnjo novega elementa v vsebnik prednostne čakalne vrste
Postavi() se uporablja za vstavljanje novega elementa v vsebnik prednostne čakalne vrste, novi element se doda v prednostno čakalno vrsto glede na svojo prioriteto. Podobno je potisnemu delovanju. Razlika je v tem, da operacija emplace() shrani nepotrebno kopijo predmeta.
Spodaj je program C++ za vgradnjo novega elementa v vsebnik prednostne čakalne vrste:
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> |
>
>Izhod
Priority Queue = 6 5 4 3 2 1>
Napotite se na konec za analizo kompleksnosti.
7. Za predstavitev tipa objekta, shranjenega kot element v priority_queue
Metoda priority_queue :: value_type je vgrajena funkcija v C++ STL, ki predstavlja vrsto predmeta, shranjenega kot element v priority_queue. Deluje kot sinonim za parameter predloge.
Sintaksa:
priority_queue::value_type variable_name>
Spodaj je program C++ za predstavitev vrste predmeta, shranjenega kot element v 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> |
>
>Izhod
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>
Napotite se na konec za analizo kompleksnosti.
Zapletenost vseh operacij:
| Metode | Časovna zapletenost | Pomožni prostor |
|---|---|---|
| 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) |
| prednostna_čakalna_vrsta_vrsta_vrednosti | O(1) | O(1) |