A C++ prioritātes rinda ir konteinera adaptera veids , kas īpaši izstrādāts tā, lai rindas pirmais elements būtu lielākais vai mazākais no visiem rindas elementiem, un elementi ir nepalielinošā vai nesamazināmā secībā (tātad mēs redzam, ka katrs rindas elementam ir prioritāte {fiksēta secība}).
Programmā C++ STL augšējais elements vienmēr ir lielākais pēc noklusējuma. Mēs varam arī mainīt to uz mazāko elementu augšpusē. Prioritārās rindas tiek veidotas maksimālā kaudzes augšdaļā, un tās izmanto masīvu vai vektoru kā iekšējo struktūru. Vienkāršiem vārdiem sakot, STL prioritātes rinda ir C++ ieviešana
// 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;> }> |
>
>Izvade
Array: 10 2 4 8 6 9 Priority Queue: 10 9 8 6 4 2>
Maksimālā kaudzes prioritātes rinda (noklusējuma shēma)
Kā izveidot minimālo kaudzi prioritārajai rindai?
Kā mēs redzējām iepriekš, prioritārā rinda pēc noklusējuma tiek ieviesta kā maksimālā kaudze programmā C++, taču tā arī sniedz mums iespēju mainīt to uz minimālo kaudzi, nododot citu parametru, vienlaikus izveidojot prioritāro rindu.
Sintakse:
priority_queue gq;>
kur,
- “int” ir elementu veids, ko vēlaties saglabāt prioritārajā rindā. Šajā gadījumā tas ir vesels skaitlis. Jūs varat aizstāt starpt ar jebkuru citu jums nepieciešamo datu tipu. “vektors” ir iekšējā konteinera veids, ko izmanto šo elementu glabāšanai. std::priority_queue nav konteiners pats par sevi, bet gan konteinera adoptētājs. Tas iesaiņo citus konteinerus. Šajā piemērā mēs izmantojam a vektors , taču varat izvēlēties citu konteineru, kas atbalsta front(), push_back() un pop_back() metodes.
- ' lielāks ' ir pielāgota salīdzināšanas funkcija. Tas nosaka, kā elementi tiek sakārtoti prioritārajā rindā. Šajā konkrētajā piemērā lielākas iestatīšanas a min-kaudze . Tas nozīmē, ka mazākais elements būs rindas augšpusē.
Maksimālās kaudzes gadījumā mums tās nebija jānorāda, jo to noklusējuma vērtības jau ir piemērotas maksimālajai kaudzei.
Piemērs:
C++
// C++ program to demonstrate> // min heap for priority queue> #include> #include> using> namespace> std;> void> showpq(> >priority_queue<>int>, vector<>int>>, lielāks<>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 |
>
>Izvade
Array: 10 2 4 8 6 9 Priority Queue : 2 4 6 8 9 10>
Minimālā kaudzes prioritātes rinda
Piezīme: Iepriekš minēto sintaksi var būt grūti atcerēties, tāpēc skaitlisko vērtību gadījumā mēs varam reizināt vērtības ar -1 un izmantot maksimālo kaudzi, lai iegūtu minimālās kaudzes efektu. Ne tikai to, ka mēs varam izmantot pielāgotu šķirošanas metodi, aizstājot lielāks ar pielāgotu salīdzinājuma funkciju.
Prioritātes rindas metodes
Šis saraksts ar visām std::priority_queue klases metodēm:
| Metode | Definīcija |
|---|---|
| priority_queue::empty() | Atgriež, vai rinda ir tukša. |
| priority_queue::size() | Atgriež rindas lielumu. |
| priority_queue::top() | Atgriež atsauci uz rindas augšējo elementu. |
| priority_queue::push() | Rindas beigās pievieno elementu “g”. |
| priority_queue::pop() | Dzēš pirmo rindas elementu. |
| priority_queue::swap() | Izmanto, lai apmainītos ar divu rindu saturu, ja rindām ir jābūt viena veida, lai gan izmēri var atšķirties. |
| priority_queue::emplace() | Izmanto, lai prioritārās rindas konteinerā ievietotu jaunu elementu. |
| prioritātes_rindas vērtības_veids | Atspoguļo objekta veidu, kas saglabāts kā prioritātes_rindas elements. Tas darbojas kā veidnes parametra sinonīms. |
Darbības prioritārajā rindā programmā C++
1. Prioritātes rindas elementu ievietošana un noņemšana
The push () metode tiek izmantota elementa ievietošanai prioritārajā rindā. Lai noņemtu elementu no prioritārās rindas, pop () metode tiek izmantota, jo tādējādi tiek noņemts elements ar augstāko prioritāti.
Zemāk ir C++ programma dažādām prioritārās rindas funkcijām:
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;> }> |
>
>Izvade
The priority queue gquiz is : 30 20 10 5 1 gquiz.size() : 5 gquiz.top() : 30 gquiz.pop() : 20 10 5 1>
Sarežģītības analīzei skatiet galu.
Piezīme : iepriekš parādīta viena no prioritārās rindas inicializācijas metodēm. Lai uzzinātu vairāk par efektīvu prioritārās rindas inicializāciju, noklikšķiniet šeit.
2. Lai piekļūtu prioritārās rindas augšējam elementam
Prioritātes rindas augšējam elementam var piekļūt, izmantojot tops() metodi.
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>>cipari;> >// 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;> }> |
>
>Izvade
Top element: 20>
Sarežģītības analīzei skatiet galu.
Piezīme: Mēs varam piekļūt tikai prioritārās rindas augšējam elementam.
3. Lai pārbaudītu, vai prioritārā rinda ir tukša, veiciet tālāk norādītās darbības.
Mēs izmantojam tukšu () metodi, lai pārbaudītu, vai prioritātes_rinda ir tukša. Šī metode atgriež:
- Patiess — tiek atgriezts, ja prioritātes rinda ir tukša un tiek apzīmēta ar 1 False — tiek izveidota, ja prioritārā rinda nav tukša vai False, un to raksturo 0
Piemērs:
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;> }> |
>
>Izvade
Contains element or False>
Sarežģītības analīzei skatiet galu.
4. Lai iegūtu/pārbaudītu prioritārās rindas lielumu
Tas nosaka prioritārās rindas lielumu. Vienkārši izsakoties, Izmērs() metode tiek izmantota, lai iegūtu elementu skaitu Prioritātes rinda .
Zemāk ir C++ programma, lai pārbaudītu prioritārās rindas lielumu:
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;> }> |
>
>Izvade
Size of the queue: 4>
Sarežģītības analīzei skatiet galu.
5. Lai apmainītu prioritārās rindas saturu ar citu līdzīga veida saturu
Apmainīt () Funkciju izmanto, lai apmainītu vienas prioritātes rindas saturu ar citu prioritāro rindu, kura ir tāda paša veida un tāda paša vai dažāda izmēra.
Zemāk ir C++ programma, lai apmainītu prioritārās rindas saturu ar citu līdzīga veida saturu:
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> |
>
>Izvade
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>
Sarežģītības analīzei skatiet galu.
6. Prioritātes rindas konteinerā ievietot jaunu elementu
Emplace () funkcija tiek izmantota, lai prioritārās rindas konteinerā ievietotu jaunu elementu, jaunais elements tiek pievienots prioritārajai rindai atbilstoši tā prioritātei. Tas ir līdzīgs push darbībai. Atšķirība ir tāda, ka emplace() darbība saglabā nevajadzīgu objekta kopiju.
Zemāk ir C++ programma, lai prioritārās rindas konteinerā ievietotu jaunu elementu:
C++
kruskals algoritms
// 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> |
>
>Izvade
Priority Queue = 6 5 4 3 2 1>
Sarežģītības analīzei skatiet galu.
7. Lai attēlotu objekta tipu, kas saglabāts kā elements priority_queue
Metode priority_queue :: value_type ir C++ STL iebūvēta funkcija, kas apzīmē objekta tipu, kas saglabāts kā prioritātes_rindas elements. Tas darbojas kā veidnes parametra sinonīms.
Sintakse:
priority_queue::value_type variable_name>
Zemāk ir C++ programma, kas attēlo objekta veidu, kas saglabāts kā priority_queue elements:
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> |
>
>Izvade
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>
Sarežģītības analīzei skatiet galu.
Visu darbību sarežģītība:
| Metodes | Laika sarežģītība | Palīgtelpa |
|---|---|---|
| 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) |
| prioritātes_rindas vērtības_veids | O(1) | O(1) |