A Prioritný front C++ je typ kontajnerového adaptéra , špecificky navrhnutý tak, že prvý prvok frontu je buď najväčší alebo najmenší zo všetkých prvkov vo fronte a prvky sú v nezvyšujúcom sa alebo neklesajúcom poradí (preto vidíme, že každý prvok frontu má prioritu {pevné poradie}).
V C++ STL je horný prvok predvolene vždy najväčší. Môžeme ho zmeniť aj na najmenší prvok v hornej časti. Prioritné fronty sú postavené na vrchole maximálnej haldy a používajú pole alebo vektor ako vnútornú štruktúru. Zjednodušene povedané, Prioritný front STL je implementácia 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;> }> |
>
>Výkon
Array: 10 2 4 8 6 9 Priority Queue: 10 9 8 6 4 2>
Max. priorita haldy (predvolená schéma)
Ako vytvoriť minimálnu haldu pre prioritný front?
Ako sme videli vyššie, prioritný front je štandardne implementovaný ako maximálna halda v C++, ale poskytuje nám tiež možnosť zmeniť ju na minimálnu haldu odovzdaním iného parametra pri vytváraní prioritného frontu.
Syntax:
priority_queue gq;>
kde,
- „int“ je typ prvkov, ktoré chcete uložiť do prioritného frontu. V tomto prípade ide o celé číslo. Môžete nahradiť int s akýmkoľvek iným typom údajov, ktorý potrebujete. „vektor“ je typ vnútorného kontajnera používaného na ukladanie týchto prvkov. std::priority_queue nie je kontajner sám o sebe, ale prijímateľ kontajnera. Obaluje ostatné nádoby. V tomto príklade používame a vektor , ale môžete si vybrať iný kontajner, ktorý podporuje metódy front(), push_back() a pop_back().
- ' väčší ‘ je vlastná porovnávacia funkcia. Toto určuje, ako sú prvky usporiadané v rámci prioritného frontu. V tomto konkrétnom príklade väčšia zostava a min-hromada . To znamená, že najmenší prvok bude v hornej časti frontu.
V prípade maximálnej haldy sme ich nemuseli špecifikovať, pretože predvolené hodnoty sú už vhodné pre maximálnu haldu.
Príklad:
C++
podreťazec reťazec java
// C++ program to demonstrate> // min heap for priority queue> #include> #include> using> namespace> std;> void> showpq(> >priority_queue<>int>, vector<>int>>, väčší<>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 |
>
>Výkon
Array: 10 2 4 8 6 9 Priority Queue : 2 4 6 8 9 10>
Minimálna priorita haldy
Poznámka: Vyššie uvedená syntax môže byť ťažko zapamätateľná, takže v prípade číselných hodnôt môžeme hodnoty vynásobiť -1 a použiť max haldu na získanie efektu min haldy. Nielen, že môžeme použiť vlastnú metódu triedenia nahradením väčší s funkciou vlastného porovnávača.
Metódy prioritného frontu
Nasledujúci zoznam všetkých metód triedy std::priority_queue:
| Metóda | Definícia |
|---|---|
| priorita_fronta::empty() | Vráti, či je front prázdny. |
| prioritný_front::veľkosť() | Vráti veľkosť frontu. |
| prioritný_front::top() | Vráti odkaz na najvyšší prvok frontu. |
| prioritný_front::push() | Pridá prvok „g“ na koniec frontu. |
| prioritný_front::pop() | Odstráni prvý prvok frontu. |
| prioritný_front::swap() | Používa sa na výmenu obsahu dvoch frontov za predpokladu, že fronty musia byť rovnakého typu, aj keď veľkosti sa môžu líšiť. |
| prioritný_front::emplace() | Používa sa na vloženie nového prvku do kontajnera prioritného frontu. |
| typ_hodnoty prioritného frontu | Predstavuje typ objektu uloženého ako prvok vo fronte priority. Funguje ako synonymum pre parameter šablóny. |
Operácie na prioritnom fronte v C++
1. Vkladanie a odstraňovanie prvkov prioritného frontu
The TAM() metóda sa používa na vloženie prvku do prioritného frontu. Ak chcete odstrániť prvok z prioritného frontu, použite pop() používa sa preto, že sa tým odstráni prvok s najvyššou prioritou.
Nižšie je uvedený program C++ pre rôzne funkcie v prioritnom rade:
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;> }> |
>
>Výkon
The priority queue gquiz is : 30 20 10 5 1 gquiz.size() : 5 gquiz.top() : 30 gquiz.pop() : 20 10 5 1>
Pozrite si koniec pre analýzu zložitosti.
Poznámka : Vyššie uvedený je jeden zo spôsobov inicializácie prioritného frontu. Ak sa chcete dozvedieť viac o efektívnej inicializácii prioritného frontu, kliknite sem.
2. Prístup k najvyššiemu prvku prioritného frontu
K hornému prvku prioritného frontu je možné pristupovať pomocou top() metóda.
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>>čísla;> >// 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;> }> |
>
>Výkon
Top element: 20>
Pozrite si koniec pre analýzu zložitosti.
Poznámka: Máme prístup len k najvyššiemu prvku v prioritnom rade.
3. Ak chcete skontrolovať, či je prioritný front prázdny alebo nie:
Používame metódu empty() na kontrolu, či je front_priority prázdny. Táto metóda vráti:
- True – Vráti sa, keď je prioritný front prázdny a je reprezentovaný 1 False – Vygeneruje sa, keď prioritný front nie je prázdny alebo False a je charakterizovaný 0
Príklad:
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;> }> |
>
>Výkon
Contains element or False>
Pozrite si koniec pre analýzu zložitosti.
4. Získať/skontrolovať veľkosť prioritného frontu
Určuje veľkosť prioritného frontu. Zjednodušene povedané, veľkosť () metóda sa používa na získanie počtu prvkov prítomných v Prioritný front .
Nižšie je uvedený program C++ na kontrolu veľkosti prioritného frontu:
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;> }> |
>
>Výkon
Size of the queue: 4>
Pozrite si koniec pre analýzu zložitosti.
5. Zameniť obsah prioritného frontu za iný podobného typu
Vymeniť () funkcia sa používa na výmenu obsahu jedného prioritného frontu s iným prioritným frontom rovnakého typu a rovnakej alebo inej veľkosti.
Nižšie je uvedený program C++ na výmenu obsahu prioritného frontu za iný podobného typu:
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> |
>
>Výkon
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>
Pozrite si koniec pre analýzu zložitosti.
6. Vložiť nový prvok do kontajnera frontu priorít
Emplace() funkcia slúži na vloženie nového prvku do kontajnera prioritného frontu, nový prvok sa pridá do prioritného frontu podľa jeho priority. Je to podobné ako pri tlači. Rozdiel je v tom, že operácia emplace() šetrí nepotrebnú kópiu objektu.
Nižšie je uvedený program C++ na vloženie nového prvku do kontajnera prioritného frontu:
java porovnateľná
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> |
>
>Výkon
Priority Queue = 6 5 4 3 2 1>
Pozrite si koniec pre analýzu zložitosti.
7. Na reprezentáciu typu objektu uloženého ako prvok vo fronte priority
Metóda priority_queue :: value_type je vstavaná funkcia v C++ STL, ktorá predstavuje typ objektu uložený ako prvok v priorite_fronty. Funguje ako synonymum pre parameter šablóny.
Syntax:
priority_queue::value_type variable_name>
Nižšie je uvedený program C++, ktorý predstavuje typ objektu uloženého ako prvok vo fronte priority:
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>>::typ_hodnoty 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> |
>
>Výkon
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>
Pozrite si koniec pre analýzu zložitosti.
Zložitosť všetkých operácií:
| Metódy | Časová zložitosť | Pomocný priestor |
|---|---|---|
| priorita_fronta::empty() | O(1) | O(1) |
| prioritný_front::veľkosť() | O(1) | O(1) |
| prioritný_front::top() | O(1) | O(1) |
| prioritný_front::push() | O(logN) | O(1) |
| prioritný_front::pop() | O(logN) | O(1) |
| prioritný_front::swap() | O(1) | O(N) |
| prioritný_front::emplace() | O(logN) | O(1) |
| typ_hodnoty prioritného frontu | O(1) | O(1) |