A Coada de prioritate C++ este un tip de adaptor de containere, proiectat special astfel încât primul element al cozii să fie cel mai mare sau cel mai mic dintre toate elementele din coadă, iar elementele să fie în ordine necrescătoare sau nedescrescătoare (deci putem vedea că fiecare elementul cozii are o prioritate {ordine fixă}).
În C++ STL, elementul superior este întotdeauna cel mai mare implicit. De asemenea, îl putem schimba cu cel mai mic element din partea de sus. Cozile prioritare sunt construite în partea de sus a heap-ului maxim și folosesc o matrice sau un vector ca structură internă. In termeni simpli, Coadă de prioritate STL este implementarea 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;> }> |
sanjay dutt și
>
>Ieșire
Array: 10 2 4 8 6 9 Priority Queue: 10 9 8 6 4 2>
Coadă de prioritate maximă heap (schemă implicită)
Cum se creează un min heap pentru coada de prioritate?
După cum am văzut mai devreme, o coadă de prioritate este implementată ca heap maxim în mod implicit în C++, dar ne oferă, de asemenea, o opțiune de a o schimba în heap minim prin trecerea unui alt parametru în timp ce creăm o coadă de prioritate.
Sintaxă:
priority_queue gq;>
Unde,
- „int” este tipul de elemente pe care doriți să le stocați în coada de prioritate. În acest caz, este un număr întreg. Puteți înlocui int cu orice alt tip de date de care aveți nevoie. „vector” este tipul de container intern folosit pentru a stoca aceste elemente. std::priority_queue nu este un container în sine, ci un adoptator de container. Înfășoară alte recipiente. În acest exemplu, folosim a vector , dar puteți alege un container diferit care acceptă metodele front(), push_back() și pop_back().
- ' mai mare ‘ este o funcție de comparare personalizată. Aceasta determină modul în care elementele sunt ordonate în coada de prioritate. În acest exemplu specific, configurații mai mari a min-heap . Înseamnă că cel mai mic element va fi în partea de sus a cozii.
În cazul heap-ului maxim, nu a trebuit să le specificăm, deoarece valorile implicite pentru acestea sunt deja potrivite pentru heap-ul maxim.
Exemplu:
C++
// C++ program to demonstrate> // min heap for priority queue> #include> #include> using> namespace> std;> void> showpq(> >priority_queue<>int>, vector<>int>>, mai mare<>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 |
>
>Ieșire
Array: 10 2 4 8 6 9 Priority Queue : 2 4 6 8 9 10>
Coadă de prioritate min Heap
Notă: Sintaxa de mai sus poate fi dificil de reținut, așa că în cazul valorilor numerice, putem înmulți valorile cu -1 și folosim max heap pentru a obține efectul min heap. Nu numai că putem folosi metoda de sortare personalizată prin înlocuire mai mare cu funcție de comparare personalizată.
Metode de coadă de prioritate
Următoarea listă a tuturor metodelor clasei std::priority_queue:
| Metodă | Definiție |
|---|---|
| priority_queue::empty() | Returnează dacă coada este goală. |
| priority_queue::size() | Returnează dimensiunea cozii. |
| priority_queue::top() | Returnează o referință la elementul cel mai de sus al cozii. |
| priority_queue::push() | Adaugă elementul „g” la sfârșitul cozii. |
| priority_queue::pop() | Șterge primul element al cozii. |
| priority_queue::swap() | Folosit pentru a schimba conținutul a două cozi, cu condiția ca cozile să fie de același tip, deși dimensiunile pot diferi. |
| priority_queue::emplace() | Folosit pentru a insera un nou element în containerul cozii prioritare. |
| priority_queue value_type | Reprezintă tipul de obiect stocat ca element într-o priority_queue. Acesta acționează ca un sinonim pentru parametrul șablon. |
Operații pe coada prioritară în C++
1. Inserarea și eliminarea elementelor unei cozi prioritare
The Apăsaţi() metoda este folosită pentru a insera un element în coada de prioritate. Pentru a elimina un element din coada de prioritate, pop() metoda este utilizată deoarece aceasta elimină elementul cu cea mai mare prioritate.
Mai jos este programul C++ pentru diferite funcții din coada de prioritate:
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;> }> |
>
>Ieșire
The priority queue gquiz is : 30 20 10 5 1 gquiz.size() : 5 gquiz.top() : 30 gquiz.pop() : 20 10 5 1>
Consultați finalul pentru analiza complexității.
Notă : Mai sus este prezentată una dintre metodele de inițializare a cozii cu prioritate. Pentru a afla mai multe despre inițializarea eficientă a cozii de prioritate, faceți clic aici.
2. Pentru a accesa elementul superior al cozii de prioritate
Elementul superior al Cozii de prioritate poate fi accesat folosind top() metodă.
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>>numere;> >// 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;> }> |
>
>Ieșire
Top element: 20>
Consultați finalul pentru analiza complexității.
Notă: Putem accesa doar elementul superior din coada de prioritate.
3. Pentru a verifica dacă coada de prioritate este goală sau nu:
Folosim metoda empty() pentru a verifica dacă priority_queue este goală. Această metodă returnează:
- Adevărat – Este returnat când coada de prioritate este goală și este reprezentată de 1 Fals – Este produs când coada de prioritate nu este goală sau Fals și este caracterizată de 0
Exemplu:
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;> }> |
>
>Ieșire
Contains element or False>
Consultați finalul pentru analiza complexității.
4. Pentru a obține/verifica dimensiunea cozii de prioritate
Acesta determină dimensiunea unei cozi prioritare. În termeni simpli, cel mărimea() metoda este folosită pentru a obține numărul de elemente prezente în Coada prioritară .
Mai jos este programul C++ pentru a verifica dimensiunea cozii de prioritate:
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;> }> |
>
>Ieșire
Size of the queue: 4>
Consultați finalul pentru analiza complexității.
5. Pentru a schimba conținutul unei cozi prioritare cu un altul de tip similar
Schimbați() funcția este utilizată pentru a schimba conținutul unei cozi de prioritate cu o altă coadă de prioritate de același tip și dimensiune identică sau diferită.
programare round robin
Mai jos este programul C++ pentru a schimba conținutul unei cozi de prioritate cu un altul de tip similar:
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> |
>
>Ieșire
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>
Consultați finalul pentru analiza complexității.
6. Pentru a introduce un nou element în containerul cozii de prioritate
plasează() funcția este utilizată pentru a insera un nou element în containerul de coadă de prioritate, noul element este adăugat la coada de prioritate în funcție de prioritatea sa. Este asemănător cu operarea prin împingere. Diferența este că operația emplace() salvează o copie inutilă a obiectului.
Mai jos este programul C++ pentru a introduce un nou element în containerul cozii de prioritate:
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> |
>
>Ieșire
Priority Queue = 6 5 4 3 2 1>
Consultați finalul pentru analiza complexității.
7. Pentru a reprezenta tipul de obiect stocat ca element într-o coadă_prioritate
Metoda priority_queue :: value_type este o funcție încorporată în C++ STL care reprezintă tipul de obiect stocat ca element într-o priority_queue. Acesta acționează ca un sinonim pentru parametrul șablon.
Sintaxă:
priority_queue::value_type variable_name>
Mai jos este programul C++ pentru a reprezenta tipul de obiect stocat ca element într-o 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> |
>
>Ieșire
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>
Consultați finalul pentru analiza complexității.
Complexitatea tuturor operațiunilor:
| Metode | Complexitatea timpului | Spațiu auxiliar |
|---|---|---|
| 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) | PE) |
| priority_queue::emplace() | O(logN) | O(1) |
| priority_queue value_type | O(1) | O(1) |