A C++ prioriteto eilė yra konteinerio adapterio tipas , specialiai sukurtas taip, kad pirmasis eilės elementas būtų didžiausias arba mažiausias iš visų eilės elementų, o elementai yra nedidėjančia arba nemažėjančia tvarka (todėl matome, kad kiekvienas eilės elementas turi prioritetą {fiksuota tvarka}).
C++ STL viršutinis elementas visada yra didžiausias pagal numatytuosius nustatymus. Taip pat galime jį pakeisti į mažiausią elementą viršuje. Prioritetinės eilės sudaromos didžiausios krūvos viršuje ir kaip vidinė struktūra naudoja masyvą arba vektorių. Paprastais žodžiais tariant, STL prioriteto eilė yra C++ diegimas
// 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;> }> |
>
>Išvestis
eilutę į sveikąjį skaičių Java
Array: 10 2 4 8 6 9 Priority Queue: 10 9 8 6 4 2>
Maks. krūvos prioriteto eilė (numatytoji schema)
Kaip sukurti prioritetinės eilės min krūvą?
Kaip matėme anksčiau, prioritetinė eilė C++ pagal numatytuosius nustatymus yra įdiegta kaip didžiausia krūva, tačiau ji taip pat suteikia mums galimybę pakeisti ją į min krūvą, perduodant kitą parametrą kuriant prioritetinę eilę.
Sintaksė:
priority_queue gq;>
kur,
- „int“ yra elementų, kuriuos norite saugoti prioritetinėje eilėje, tipas. Šiuo atveju tai yra sveikasis skaičius. Galite pakeisti tarpt su bet kokiu kitu jums reikalingu duomenų tipu. „vektorius“ yra vidinio konteinerio tipas, naudojamas šiems elementams saugoti. std::priority_queue yra ne pats konteineris, o konteinerio pritaikytojas. Jis apvynioja kitus konteinerius. Šiame pavyzdyje mes naudojame a vektorius , bet galite pasirinkti kitą konteinerį, kuris palaiko front(), push_back() ir pop_back() metodus.
- ' didesnis “ yra tinkinta palyginimo funkcija. Tai nustato, kaip elementai išdėstomi prioritetinėje eilėje. Šiame konkrečiame pavyzdyje didesnės sąrankos a min-krūva . Tai reiškia, kad mažiausias elementas bus eilės viršuje.
Didžiausios krūvos atveju mums nereikėjo jų nurodyti, nes numatytosios jų reikšmės jau tinka maksimaliai krūvai.
Pavyzdys:
C++
// C++ program to demonstrate> // min heap for priority queue> #include> #include> using> namespace> std;> void> showpq(> >priority_queue<>int>, vector<>int>>, didesnis<>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 |
>
>Išvestis
Array: 10 2 4 8 6 9 Priority Queue : 2 4 6 8 9 10>
Min. krūvos prioriteto eilė
Pastaba: Aukščiau pateiktą sintaksę gali būti sunku prisiminti, todėl skaitinių reikšmių atveju reikšmes galime padauginti iš -1 ir naudoti max heap, kad gautume min krūvos efektą. Ne tik tai, kad pakeisdami galime naudoti pasirinktinį rūšiavimo metodą didesnis su pasirinktine palyginimo funkcija.
Pirmumo eilės metodai
Šis visų std::priority_queue klasės metodų sąrašas:
| Metodas | Apibrėžimas |
|---|---|
| priority_queue::empty() | Grąžina, ar eilė tuščia. |
| prioriteto_eilė::dydis() | Grąžina eilės dydį. |
| priority_queue::top() | Grąžina nuorodą į aukščiausią eilės elementą. |
| prioriteto_eilė::push() | Eilės pabaigoje prideda elementą „g“. |
| priority_queue::pop() | Ištrina pirmąjį eilės elementą. |
| prioriteto_eilė::swap() | Naudojamas dviejų eilių turiniui sukeisti, jei eilės turi būti to paties tipo, nors dydžiai gali skirtis. |
| priority_queue::emplace() | Naudojamas naujam elementui įterpti į prioritetinės eilės konteinerį. |
| prioriteto_eilės vertės_tipas | Nurodo objekto tipą, saugomą kaip prioriteto_eilės elementą. Jis veikia kaip šablono parametro sinonimas. |
Operacijos prioritetinėje eilėje C++
1. Prioritetinės eilės elementų įterpimas ir pašalinimas
The stumti () metodas naudojamas elementui įterpti į prioritetinę eilę. Norėdami pašalinti elementą iš prioritetinės eilės, pop () metodas naudojamas, nes taip pašalinamas elementas, turintis didžiausią prioritetą.
Žemiau yra C++ programa, skirta įvairioms funkcijoms prioritetinėje eilėje:
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;> }> |
>
>Išvestis
The priority queue gquiz is : 30 20 10 5 1 gquiz.size() : 5 gquiz.top() : 30 gquiz.pop() : 20 10 5 1>
Dėl sudėtingumo analizės žr. pabaigą.
Pastaba : Aukščiau parodytas vienas iš prioritetinės eilės inicijavimo metodų. Norėdami sužinoti daugiau apie efektyvų prioritetinės eilės inicijavimą, spustelėkite čia.
2. Norėdami pasiekti viršutinį prioritetinės eilės elementą
Viršutinį prioritetinės eilės elementą galima pasiekti naudojant viršuje () metodas.
C++
abėcėlė sunumeruota
// 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>>skaičiai;> >// 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;> }> |
>
>Išvestis
Top element: 20>
Dėl sudėtingumo analizės žr. pabaigą.
Pastaba: Galime pasiekti tik viršutinį prioritetinės eilės elementą.
3. Norėdami patikrinti, ar prioritetinė eilė tuščia, ar ne:
Naudojame tuščią () metodą, kad patikrintume, ar prioriteto_eilė tuščia. Šis metodas grąžina:
- Tiesa – grąžinama, kai prioritetinė eilė tuščia ir vaizduojama kaip 1 Netiesa – sukuriama, kai prioritetinė eilė nėra tuščia arba klaidinga ir apibūdinama 0
Pavyzdys:
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;> }> |
shweta tiwari
>
>Išvestis
Contains element or False>
Dėl sudėtingumo analizės žr. pabaigą.
4. Norėdami gauti / patikrinti prioritetinės eilės dydį
Jis nustato prioritetinės eilės dydį. Paprastais žodžiais tariant, dydis () metodas naudojamas norint gauti elementų skaičių Prioritetinė eilė .
Žemiau yra C++ programa, skirta patikrinti prioritetinės eilės dydį:
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;> }> |
>
>Išvestis
Size of the queue: 4>
Dėl sudėtingumo analizės žr. pabaigą.
5. Sukeisti prioritetinės eilės turinį į kitą panašaus tipo turinį
Sukeisti () Funkcija naudojama vienos prioritetinės eilės turiniui pakeisti kita to paties tipo ir tokio pat arba skirtingo dydžio prioritetine eile.
Žemiau yra C++ programa, skirta pakeisti prioritetinės eilės turinį į kitą panašaus tipo:
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> |
>
>Išvestis
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>
Dėl sudėtingumo analizės žr. pabaigą.
6. Į prioritetinės eilės konteinerį įtraukti naują elementą
Emplace () funkcija naudojama naujam elementui įterpti į prioritetinės eilės konteinerį, naujas elementas įtraukiamas į prioritetinę eilę pagal jo prioritetą. Tai panašu į stūmimo operaciją. Skirtumas tas, kad emplace() operacija išsaugo nereikalingą objekto kopiją.
Žemiau yra C++ programa, skirta naujam elementui įdėti į prioritetinės eilės konteinerį:
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> |
java localdatetime
>
>Išvestis
Priority Queue = 6 5 4 3 2 1>
Sudėtingumo analizės pabaigoje žr.
7. Atvaizduoti objekto tipą, saugomą kaip prioriteto_eilės elementą
Metodas „Priority_queue :: value_type“ yra C++ STL įtaisyta funkcija, kuri parodo objekto tipą, saugomą kaip prioriteto_eilės elementas. Jis veikia kaip šablono parametro sinonimas.
Sintaksė:
priority_queue::value_type variable_name>
Žemiau yra C++ programa, vaizduojanti objekto tipą, saugomą kaip prioriteto_eilės elementą:
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> |
>
>Išvestis
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>
Dėl sudėtingumo analizės žr. pabaigą.
Visų operacijų sudėtingumas:
| Metodai | Laiko sudėtingumas | Pagalbinė erdvė |
|---|---|---|
| priority_queue::empty() | O(1) | O(1) |
| prioriteto_eilė::dydis() | O(1) windows.open javascript | O(1) |
| priority_queue::top() | O(1) | O(1) |
| prioriteto_eilė::push() | O(logN) | O(1) |
| priority_queue::pop() | O(logN) | O(1) |
| prioriteto_eilė::swap() | O(1) | O(N) |
| priority_queue::emplace() | O(logN) | O(1) |
| prioriteto_eilės vertės_tipas | O(1) | O(1) |