A C++-prioriteettijono on konttisovitintyyppi, joka on erityisesti suunniteltu siten, että jonon ensimmäinen elementti on joko suurin tai pienin kaikista jonon elementeistä, ja elementit ovat ei-nousevassa tai ei-laskevassa järjestyksessä (täten voimme nähdä, että jokainen jonon elementillä on prioriteetti {kiinteä järjestys}).

C++ STL:ssä yläelementti on aina oletuksena suurin. Voimme myös muuttaa sen pienimmäksi elementiksi yläreunassa. Prioriteettijonot rakennetaan maksimikeon päälle ja käyttävät taulukkoa tai vektoria sisäisenä rakenteena. Yksinkertaisin termein, STL-prioriteettijono on C++:n toteutus

// 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;> }>

Lähtö

Array: 10 2 4 8 6 9 Priority Queue: 10 9 8 6 4 2 

Max Keon prioriteettijono (oletusmalli)

Kuinka luodaan prioriteettijonolle minimikeko?

Kuten näimme aiemmin, prioriteettijono toteutetaan oletusarvoisesti max-keona C++:ssa, mutta se tarjoaa myös mahdollisuuden muuttaa se minimikekoksi välittämällä toinen parametri samalla kun luodaan prioriteettijono.

Syntaksi:

priority_queue  gq; 

missä,

'int' on elementtien tyyppi, jotka haluat tallentaa prioriteettijonoon. Tässä tapauksessa se on kokonaisluku. Voit vaihtaa int minkä tahansa muun tarvitsemasi tietotyypin kanssa. 'vektori' on näiden elementtien tallentamiseen käytettävän sisäisen säiliön tyyppi. std::priority_queue ei ole säilö sinänsä, vaan kontin omaksuja. Se käärii muut säiliöt. Tässä esimerkissä käytämme a vektori , mutta voit valita toisen säilön, joka tukee front(-), push_back()- ja pop_back()-menetelmiä.
• ' suurempi ' on mukautettu vertailutoiminto. Tämä määrittää, kuinka elementit järjestetään prioriteettijonossa. Tässä esimerkissä suuremmat asetukset a min-kasa . Se tarkoittaa, että pienin elementti on jonon yläosassa.

Max-keon tapauksessa meidän ei tarvinnut määrittää niitä, koska niiden oletusarvot sopivat jo maksimikekolle.

Esimerkki:

C++

// C++ program to demonstrate> // min heap for priority queue> #include> #include> using> namespace> std;> void> showpq(> > priority_queue <> int> , vector <> int> >, suurempi <> 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 , suurempi > gquiz(arr, arr + 6); cout < < 'Array: '; showArray(arr, 6); cout < < 'Priority Queue : '; showpq(gquiz); return 0; }>

Lähtö

Array: 10 2 4 8 6 9 Priority Queue : 2 4 6 8 9 10 

Vähimmäiskeon prioriteettijono

Huomautus: Yllä olevaa syntaksia voi olla vaikea muistaa, joten numeeristen arvojen tapauksessa voimme kertoa arvot -1:llä ja käyttää maksimikekoa saadakseen min kason vaikutuksen. Ei vain sitä, että voimme käyttää mukautettua lajittelumenetelmää korvaamalla suurempi mukautetulla vertailutoiminnolla.

Priority Queue -menetelmät

Seuraava luettelo kaikista std::priority_queue-luokan menetelmistä:

Menetelmä	Määritelmä
prioriteettijono::tyhjä()	Palauttaa, onko jono tyhjä.
prioriteettijono::koko()	Palauttaa jonon koon.
prioriteettijono::top()	Palauttaa viittauksen jonon ylimpään elementtiin.
prioriteettijono::push()	Lisää elementin 'g' jonon loppuun.
prioriteettijono::pop()	Poistaa jonon ensimmäisen elementin.
priority_queue::swap()	Käytetään kahden jonon sisällön vaihtamiseen edellyttäen, että jonojen on oltava samaa tyyppiä, vaikka koot voivat vaihdella.
priority_queue::emplace()	Käytetään uuden elementin lisäämiseen prioriteettijonosäilöön.
prioriteettijonon arvon_tyyppi	Edustaa prioriteettijonon elementiksi tallennetun objektin tyyppiä. Se toimii malliparametrin synonyyminä.

Toiminnot prioriteettijonossa C++:ssa

1. Prioriteettijonon elementtien lisääminen ja poistaminen

The työntää() -menetelmää käytetään elementin lisäämiseen prioriteettijonoon. Voit poistaa elementin prioriteettijonosta pop() menetelmää käytetään, koska se poistaa korkeimman prioriteetin omaavan elementin.

Alla on C++-ohjelma prioriteettijonon eri funktioille:

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;> }>

Lähtö

The priority queue gquiz is : 30 20 10 5 1 gquiz.size() : 5 gquiz.top() : 30 gquiz.pop() : 20 10 5 1 

Katso monimutkaisuusanalyysin loppu.

Huomautus : Yllä on yksi prioriteettijonon alustusmenetelmistä. Saat lisätietoja prioriteettijonon tehokkaasta alustamisesta napsauttamalla tätä.

2. Pääset prioriteettijonon ylimpään elementtiin

Priority Queue:n ylimpään elementtiin pääsee käsiksi käyttämällä top() menetelmä.

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> >numerot;> > // 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;> }>

Lähtö

Top element: 20 

Katso monimutkaisuusanalyysin loppu.

Huomautus: Voimme käyttää vain prioriteettijonon ylintä elementtiä.

3. Tarkista, onko prioriteettijono tyhjä vai ei:

Käytämme tyhjä()-menetelmää tarkistaaksemme, onko priority_queue tyhjä. Tämä menetelmä palauttaa:

True – Se palautetaan, kun prioriteettijono on tyhjä ja sitä edustaa 1 False – Se tuotetaan, kun prioriteettijono ei ole tyhjä tai False ja sille on ominaista 0

Esimerkki:

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;> }>

Lähtö

Contains element or False 

Katso monimutkaisuusanalyysin loppu.

4. Hae/tarkista prioriteettijonon koko

Se määrittää prioriteettijonon koon. Yksinkertaisesti sanottuna koko() -menetelmää käytetään määrittämään elementtien lukumäärä Prioriteettijono .

Alla on C++-ohjelma prioriteettijonon koon tarkistamiseksi:

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;> }>

Lähtö

Size of the queue: 4 

Katso loppu monimutkaisuusanalyysiä varten.

5. Ensisijaisen jonon sisällön vaihtaminen toisen samantyyppiseen jonoon

Vaihtaa() -toimintoa käytetään yhden prioriteettijonon sisällön vaihtamiseen toisen prioriteettijonon kanssa, joka on samantyyppinen ja samankokoinen tai erikokoinen.

Alla on C++-ohjelma prioriteettijonon sisällön vaihtamiseksi toiseen samantyyppiseen jonoon:

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>

Lähtö

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 

Katso monimutkaisuusanalyysin loppu.

6. Aseta uusi elementti prioriteettijonosäilöön

Emplace() -toimintoa käytetään uuden elementin lisäämiseen prioriteettijonosäilöön, uusi elementti lisätään prioriteettijonoon sen prioriteetin mukaan. Se on samanlainen kuin push-toiminto. Erona on, että emplace()-toiminto säästää tarpeettoman kopion objektista.

Alla on C++-ohjelma uuden elementin lisäämiseksi prioriteettijonosäilöö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>

Lähtö

Priority Queue = 6 5 4 3 2 1 

Katso monimutkaisuusanalyysin loppu.

7. Esittää prioriteettijonon elementtinä tallennetun objektin tyypin

Prioriteettijono :: arvotyyppi -menetelmä on C++ STL:n sisäänrakennettu funktio, joka edustaa prioriteettijonon elementtinä tallennetun objektin tyyppiä. Se toimii malliparametrin synonyyminä.

Syntaksi:

priority_queue::value_type variable_name 

Alla on C++-ohjelma, joka edustaa priority_queue-elementiksi tallennetun objektin tyyppiä:

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> >::arvo_tyyppi 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>

Lähtö

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 

Katso monimutkaisuusanalyysin loppu.

Kaikkien toimintojen monimutkaisuus:

menetelmät	Aika monimutkaisuus	Aputila
prioriteettijono::tyhjä()	O(1)	O(1)
prioriteettijono::koko()	O(1)	O(1)
prioriteettijono::top()	O(1)	O(1)
prioriteettijono::push()	O(logN)	O(1)
prioriteettijono::pop()	O(logN)	O(1)
priority_queue::swap()	O(1)	PÄÄLLÄ)
priority_queue::emplace()	O(logN)	O(1)
prioriteettijonon arvon_tyyppi	O(1)	O(1)