Hvordan bruke C ++ Priority_queue?

I C ++ er en kø en listedatastruktur der det første elementet som blir lagt i listen er det første elementet som blir fjernet, når fjerning skal finne sted. En prioritert kø i C ++ er lik, men har en viss bestilling; Det er elementet med den største verdien som først fjernes. Prioritetskøen kan fremdeles konfigureres slik at det er elementet med minst mulig verdi som fjernes først. Enhver kø må ha minst trykk() funksjon og pop () funksjon. De trykk() Funksjon legger til et nytt element bak. For normal kø, pop () Funksjon fjerner det første elementet som noen gang er skjøvet inn. For prioriteringskøen, pop () Funksjon fjerner elementet med høyest prioritet, som kan være det største eller minste, avhengig av bestillingsskjemaet.

For å bruke C ++ Priority_queue, skal programmet begynne med kode som:

#inkludere
#inkludere
ved hjelp av navneområdet STD;

Det inkluderer købiblioteket inn i programmet.

For å fortsette å lese, burde leseren hatt en grunnleggende kunnskap om C++.

Artikkelinnhold

• Grunnleggende konstruksjon
• Viktige medlemsfunksjoner
• Andre prioriterte køfunksjoner
• Strengdata
• Andre prioriterte køskonstruksjoner
• Konklusjon

Grunnleggende konstruksjon

Datastrukturen må konstrueres først før den kan brukes. Konstruksjon her betyr å gi et objekt fra køklassen på biblioteket. Køobjektet må da ha et navn gitt til det av programmereren. Den enkleste syntaksen for å opprette en prioritert kø er:

Priority_queue Queuename;

Med denne syntaksen fjernes den største verdien først. Et eksempel på oppstart er:

Priority_queue PQ;

eller

Priority_queue PQ;

Vektoren og deque er to datastrukturer i C++. En prioriterings_queue kan opprettes med en av dem. Syntaksen for å lage en prioritert kø fra vektorstrukturen er:

Priority_queue, Sammenlign> PQ;

Et eksempel på denne instantieringen er:

Priority_queue, mindre > PQ;

Legg merke til gapet mellom> og> på slutten av erklæringen. Dette for å forhindre forvirring med >>. Standard sammenligningskode er "mindre", noe som betyr den største, og ikke nødvendigvis den første verdien, vil bli fjernet først. Så skaperklæringen kan ganske enkelt skrives som:

Priority_queue > PQ;

Hvis den minste verdien skal fjernes først, må uttalelsen være:

Priority_queue, større > PQ;

Viktige medlemsfunksjoner

Push () -funksjonen
Denne funksjonen skyver en verdi, som er dens argument, inn i prioriterings_queue. Det returnerer tomrom. Følgende kode illustrerer dette:

Priority_queue PQ;
pq.Push (10);
pq.Push (30);
pq.Push (20);
pq.Push (50);
pq.Push (40);

Denne prioriterte_queue har mottatt 5 heltallverdier i størrelsesorden 10, 30, 20, 50, 40. Hvis alle disse elementene skal poppes ut av prioriteringskøen, vil de komme ut i størrelsesorden 50, 40, 30, 20, 10.

Pop () -funksjonen
Denne funksjonen fjerner fra prioriterings_queue Verdien med høyest prioritet. Hvis sammenligningskoden er "større", vil den fjerne elementet med den minste verdien. Hvis det blir kalt igjen, fjerner det neste element med den minste verdien av resten; Kalt igjen, fjerner den den neste minste verdien som er til stede, og så videre. Det returnerer tomrom. Følgende kode illustrerer dette:

Priority_queue, større > PQ;
pq.push ('a');
pq.push ('c');
pq.push ('b');
pq.push ('e');
pq.push ('d');

Legg merke til at for å kalle en medlemsfunksjon, må navnet på objektet følges av en prikk, og deretter funksjonen.

Topp () -funksjonen
De pop () Funksjonen fjerner neste verdi av høyeste prioritet, men returnerer den ikke, som pop () er en ugyldig funksjon. Bruke topp() funksjon for å kjenne verdien av høyeste prioritet som må fjernes neste. De topp() Funksjon returnerer en kopi av verdien av høyeste prioritet i prioriterings_queue. Følgende kode, der den neste verdien av høyeste prioritet er minst mulig verdi, illustrerer dette

Priority_queue, større > PQ;
pq.push ('a'); pq.push ('c'); pq.push ('b'); pq.push ('e'); pq.push ('d');
char ch1 = pq.topp(); pq.pop ();
char ch2 = pq.topp(); pq.pop ();
char ch3 = pq.topp(); pq.pop ();
char ch4 = pq.topp(); pq.pop ();
Char CH5 = PQ.topp(); pq.pop ();
cout<

Utgangen er 'A "B" C "D" e'.

Den tomme () funksjonen
Hvis en programmerer bruker topp() Funksjon på en tom Priority_queue, etter den vellykkede samlingen, ville han motta en feilmelding som:

Segmenteringsfeil (kjernedumped)

Så sjekk alltid om prioriteringskøen ikke er tom før du bruker topp() funksjon. De tømme() Medlemsfunksjonen returnerer en bool, sant, hvis køen er tom, og falsk hvis køen ikke er tom. Følgende kode illustrerer dette:

Priority_queue PQ;
int i1 = 10; int i2 = 30; int i3 = 20; int i4 = 50; int i5 = 40;
pq.Push (i1); pq.Push (i2); pq.Push (i3); pq.Push (i4); pq.Push (i5);
samtidig som(!pq.tømme())

cout << pq.top() << ";
pq.pop ();

cout << '\n';

Andre prioriterte køfunksjoner

Størrelsen () -funksjonen
Denne funksjonen returnerer lengden på prioriteringskøen, som følgende kode illustrerer:

Priority_queue PQ;
int i1 = 10; int i2 = 30; int i3 = 20; int i4 = 50; int i5 = 40;
pq.Push (i1); pq.Push (i2); pq.Push (i3); pq.Push (i4); pq.Push (i5);
int len ​​= pq.størrelse();
cout << len << '\n';

Utgangen er 5.

Bytting () -funksjonen
Hvis to prioriterte_queues er av samme type og størrelse, kan de byttes av denne funksjonen, som følgende kode viser:

Priority_queue PQ1;
int i1 = 10; int i2 = 30; int i3 = 20; int i4 = 50; int i5 = 40;
PQ1.Push (i1); PQ1.Push (i2); PQ1.Push (i3); PQ1.Push (i4); PQ1.Push (i5);
Priority_queue PQA;
int it1 = 1; int it2 = 3; int it3 = 2; int it4 = 5; int it5 = 4;
PQA.push (it1); PQA.push (it2); PQA.push (it3); PQA.Push (IT4); PQA.Push (IT5);
PQ1.Swap (PQA);
samtidig som(!PQ1.tømme())

cout << pq1.top() << ";
PQ1.pop ();
cout<<'\n';
samtidig som(!PQA.tømme())

cout << pqA.top() << ";
PQA.pop ();
cout<<'\n';

Utgangen er:

5 4 3 2 1
50 40 30 20 10

Emplaten () fuksjonen
De Emplace () Funksjon ligner på push -funksjonen. Følgende kode illustrerer dette:

Priority_queue PQ1;
int i1 = 10; int i2 = 30; int i3 = 20; int i4 = 50; int i5 = 40;
PQ1.Emplace (i1);
PQ1.Emplace (I2);
PQ1.Emplace (i3);
PQ1.Emplace (i4);
PQ1.Emplace (i5);
samtidig som(!PQ1.tømme())

cout << pq1.top() << ";
PQ1.pop ();
cout<<'\n';

Utgangen er:

50 40 30 20 10

Strengdata

Når du sammenligner strenger, bør strengklassen brukes og ikke direkte bruk av strenglitteralene fordi den ville sammenligne pekere og ikke de faktiske strengene. Følgende kode viser hvordan strengklassen brukes:

#inkludere
Priority_queue PQ1;
Streng S1 = String ("Pen"),
S2 = streng ("Blyant"),
S3 = String ("Treningsbok"),
S4 = String ("Tekstbok"),
s5 = streng ("linjal");
PQ1.Push (S1);
PQ1.Push (S2);
PQ1.Push (S3);
PQ1.Push (S4);
PQ1.Push (S5);
samtidig som(!PQ1.tømme())

cout << pq1.top() << " ";
PQ1.pop ();
cout<<'\n';

Utgangen er:

tekstbok linjal blyantpenn treningsbok

Andre prioriterte køskonstruksjoner

Eksplisitt skapelse fra en vektor
En prioriteringskø kan opprettes eksplisitt fra en vektor som følgende kode viser:

#inkludere
vektor VTR = 10, 30, 20, 50, 40;
Priority_queue PQ (VTR.Begynn (), VTR.slutt());
samtidig som(!pq.tømme())

cout << pq.top() << ";
pq.pop ();
cout<<'\n';

Utgangen er: 50 40 30 20 10. Denne gangen må vektorhodet også inkluderes. Argumentene for konstruktørfunksjonen tar start- og sluttpekerne til vektoren. Datatypen for vektoren og datatypen for Priority_queue må være den samme.

For å gjøre minst mulig verdi prioritet, ville erklæringen for konstruktøren være:

Priority_queue, større> int >> PQ (VTR.Begynn (), VTR.slutt());

Eksplisitt skapelse fra en matrise
En prioriteringskø kan opprettes eksplisitt fra en matrise, da følgende kode viser:

int arr [] = 10, 30, 20, 50, 40;
Priority_queue PQ (arr, arr+5);
samtidig som(!pq.tømme())

cout << pq.top() << ";
pq.pop ();
cout<<'\n';

Utgangen er: 50 40 30 20 10. Argumentene for konstruktørfunksjonen tar start- og sluttpekene til matrisen. ARR returnerer startpekeren, “ARR+5” returnerer pekeren like forbi matrisen, og 5 er størrelsen på matrisen. Datatypen for matrisen og datatypen for Priority_queue må være den samme.

For å gjøre minst mulig verdi prioritet, ville erklæringen for konstruktøren være:

Priority_queue, større > PQ (arr, arr+5);

Merk: I C ++ kalles Priority_queue faktisk en adapter, ikke bare en beholder.

Tilpasset sammenligningskode

Å ha alle verdier i prioriteringskøen som stiger opp eller alt synker er ikke det eneste alternativet for prioriteringskøen. For eksempel er en liste over 11 heltall for en maksimal haug:

88, 86, 87, 84, 82, 79,74, 80, 81 ,,, 64, 69

Den høyeste verdien er 88. Dette blir fulgt av to tall: 86 og 87, som er mindre enn 88. Resten av tallene er mindre enn disse tre tallene, men egentlig ikke i orden. Det er to tomme celler i listen. Tallene 84 og 82 er mindre enn 86. Tallene 79 og 74 er mindre enn 87. Tallene 80 og 81 er mindre enn 84. Tallene 64 og 69 er mindre enn 79.

Plasseringen av tallene følger Max -Heap -kriteriene - se senere. For å gi en slik ordning for Priority_queue, må programmereren oppgi sin egen sammenligningskode - se senere.

Konklusjon

En C ++ Priority_queue er en første-første-ut-kø. Medlemsfunksjonen, trykk(), Legger en ny verdi i køen. Medlemsfunksjonen, topp(), leser toppverdien i køen. Medlemsfunksjonen, pop (), fjerner uten å returnere toppverdien på køen. Medlemsfunksjonen, tømme(), sjekker om køen er tom. Imidlertid skiller Priority_queue seg fra køen, ved at den følger noen prioriteringsalgoritme. Det kan være størst, fra første til sist, eller minst, fra første til sist. Kriteriene (algoritmen) kan også være programmeringsdefinert.