Meny

Prioritert kødatastruktur i C ++ med illustrasjon

  • Hoved
  • Annen
  • Prioritert kødatastruktur i C ++ med illustrasjon

priority queue data structure c with illustration

Prøv Instrumentet Vårt For Å Eliminere Problemer

Introduksjon til prioritert kø i C ++ med illustrasjon.

Priority Queue er en utvidelse av køen som vi diskuterte i vår siste opplæring.

Det ligner på køen i visse aspekter, og likevel skiller det seg fra den vanlige køen i følgende punkter:

  • Hvert element i prioritetskøen er knyttet til en prioritet.
  • Elementet med høyest prioritet er det første elementet som fjernes fra køen.
  • Hvis mer enn ett element har samme prioritet, blir bestillingen i køen vurdert.

=> Klikk her for den absolutte C ++ treningsserien.

Prioritetskø i C ++

Vi kan visualisere prioritetskøen som en modifisert versjon av køen, bortsett fra at når varen skal tas av køen, blir elementet med høyest prioritet hentet først. Så vi foretrekker å bruke prioritetskøene i stedet for køene når vi trenger å behandle elementene basert på prioritet.

Hva du vil lære:

Grunnleggende operasjoner

La oss diskutere noen av de grunnleggende operasjonene som støttes av prioritetskøen.

  • Sett inn (element, prioritet): Setter inn et element i prioritetskøen med en gitt prioritet.
  • getHighestPriority (): Returnerer et element med høyest prioritet.
  • deleteHighestPriority (): Fjerner et element med høyest prioritet.

Bortsett fra operasjonene ovenfor, kan vi også bruke de vanlige køoperasjonene som isEmpty (), isFull () og peek ().

Illustrasjon

La oss se en illustrasjon av prioritetskøen. For enkelhets skyld vil vi bruke ASCII-tegn som elementer i prioritetskøen. Jo høyere ASCII-verdi, jo høyere er prioriteten.

Starttilstand - Prioritetskø (PQ) - {} => tom

illustrasjon av prioritetskøen

Fra illustrasjonen ovenfor ser vi at innsatsoperasjonen ligner på en vanlig kø. Men når vi kaller “deleteHighestPriority” for prioritetskøen, fjernes elementet med høyest prioritet først.

Derfor første gang når vi kaller denne funksjonen, blir element O fjernet mens andre gang, blir elementet M fjernet ettersom det har høyere prioritet enn G og A.

Implementering av prioritetskøer i C ++

Prioritetskøer kan implementeres ved hjelp av:

# 1) Arrays / Koblede lister

Vi kan implementere prioritetskøene ved hjelp av arrays, og dette er den enkleste implementeringen for prioritetskøene.

For å representere elementene i prioritetskøen, kan vi bare erklære en struktur som nedenfor:

struct pq_item{ int item; int priority; };

Vi har også erklært prioriteten for hvert element.

For å sette inn et nytt element i prioritetskøen, må vi bare sette inn elementet på slutten av matrisen.

For å få elementet fra køen ved hjelp av getHighestPriority (), må vi krysse matrisen fra starten og returnere elementet med høyest prioritet.

På samme måte, for å fjerne elementet fra køen ved hjelp av deleteHighestPriority-operasjonen, må vi krysse hele matrisen og slette elementet med høyest prioritet. Flytt deretter alle de andre elementene etter det slettede elementet, en posisjon tilbake.

Vi kan også implementere prioritetskøen ved hjelp av en koblet liste. Vi kan utføre alle operasjonene på en lignende måte som arrays. Den eneste forskjellen er at vi ikke trenger å flytte elementene etter å ha kalt deleteHighestPriority.

# 2) Hauger

Å bruke dynger for å implementere en prioritert kø er den mest effektive måten, og det gir mye bedre ytelse sammenlignet med de lenkede lister og matriser. I motsetning til den tilknyttede listen og matrisen tar heapimplementering O (logn) tid for å sette inn og slette operasjoner i prioritetskøen. Få drift, getHighestPriority tar O (1) tid.

# 3) Innebygd prioritetskø i standardmalbibliotek (STL) i C ++

I C ++ har vi en prioritetskø som en containeradaptiv klasse, designet på en slik måte at det høyeste elementet er det første elementet i køen og alle elementene er i avtagende rekkefølge.

Dermed har hvert element i prioritetskøen en fast prioritet.

Vi har klasse i STL, som inneholder prioritering av køimplementering.

De forskjellige operasjonene som støttes av prioritetskøen er som følger:

  1. prioritering_størrelse :: størrelse (): Returnerer størrelsen på køen.
  2. prioritets_kjøring :: tom (): Sjekker om køen er tom og returnerer statusen.
  3. prioritering_kjøring :: topp (): Returnerer en referanse til det øverste elementet i prioritetskøen.
  4. prioritering_skue :: trykk (): Legger til et element på slutten av prioritetskøen.
  5. prioritets_skue :: pop (): Fjerner det første elementet fra prioritetskøen.
  6. prioritets_kjøp :: bytt (): Brukes til å bytte innholdet i en prioritetskø med en annen av samme type og størrelse.
  7. prioritert køverditype: Verditype gir typen element som er lagret i en prioritetskø. Dette fungerer også som et synonym for malparameteren.
  8. prioritering_kurs :: emplace (): Brukes til å sette inn et nytt element i prioritetskøbeholderen øverst i køen.

I neste program vil vi se funksjonaliteten til prioritetskøen i STL i C ++.

#include #include using namespace std; void displaypq(priority_queue pq) { priority_queue pqueue = pq; while (!pqueue.empty()) { cout << ' ' << pqueue.top(); pqueue.pop(); } cout << ' '; } int main () { priority_queue pq; pq.push(1); pq.push(3); pq.push(5); pq.push(7); pq.push(9); cout << 'Size of the queue(pq.size()): ' << pq.size(); cout << ' Top element of the queue(pq.top()): ' << pq.top(); cout << ' The priority queue pq is : '; displaypq(pq); cout << ' Priority queue, after pq.pop() operation : '; pq.pop(); displaypq(pq); return 0; }

Produksjon:

hvordan du starter et java-prosjekt

Størrelse på køen (pq.størrelse ()): 5
Toppelement i køen (pq.top ()): 9
Prioritetskøen pq er: 9 7 5 3 1
Prioritetskø, etter pq.pop () -operasjon: 7 5 3 1

Java-implementering for prioritetskø

Prioritetskø i java er en spesiell kø der alle elementene i køen er bestilt i henhold til naturlig bestilling eller tilpasset bestilling ved hjelp av en komparator som følger med køen.

En prioritetskø i Java ser ut som vist nedenfor:

Java-implementering for prioritetskø

I Java-prioritetskø er elementene ordnet slik at det minste elementet er foran i køen og det største elementet er på baksiden av køen. Så når vi fjerner elementet fra prioritetskøen, er det alltid det minste elementet som fjernes.

Klassen som implementerer prioritetskøen i Java er 'PriorityQueue' og er en del av samlingsrammen til Java. Den implementerer Java-grensesnittet til Java.

Følgende er klassehierarkiet for Java PriorityQueue-klassen.

klassehierarki for Java PriorityQueue-klasse

Nedenfor er et eksempel på prioritert køfunksjonalitet med heltall som elementer i Java.

import java.util.*; class Main { public static void main(String args()) { // Create empty priority queue PriorityQueue priority_Queue = new PriorityQueue(); // Adding items to the priority_Queue using add() priority_Queue.add(1); priority_Queue.add(3); priority_Queue.add(5); priority_Queue.add(7); // display the most priority element System.out.println('peek()::Head value:' + priority_Queue.peek()); // Print all elements in Priotity queue System.out.println('The priority queue:'); Iterator itr = priority_Queue.iterator(); while (itr.hasNext()) System.out.print(itr.next() + ' '); // poll() function to remove the queue elements priority_Queue.poll(); System.out.println(' After poll() function, priority queue:'); Iterator itr2 = priority_Queue.iterator(); while (itr2.hasNext()) System.out.print(itr2.next() + ' '); // remove() function with priority queue priority_Queue.remove(5); System.out.println(' After Remove(5) function, priority queue:'); Iterator itr3 = priority_Queue.iterator(); while (itr3.hasNext()) System.out.print(itr3.next() + ' '); // Check if an element is present using contains() boolean b = priority_Queue.contains(3); System.out.println ( ' Priority queue contains 3?: ' + b); // use toArray() function to get objects from the queue and display the array elements Object() arr = priority_Queue.toArray(); System.out.println ( 'Array elements: '); for (int i = 0; i

Produksjon:

peek () :: Hodeverdi: 1
Prioritetskøen:
1 3 5 7
Etter avstemningsfunksjon (), prioritetskø:
3 7 5
Etter Fjern (5) -funksjonen, prioritetskø:
3 7
Prioritetskø inneholder 3 ?: sant
Array-elementer:
Verdi: 3
Verdi: 7

I programmet ovenfor bruker vi PriorityQueue-klassen til Java for å lage et objekt av PriorityQueue som inneholder et Integer-objekt. Vi legger til elementer i køen ved hjelp av 'legg til' -funksjonen. Deretter kalles avstemningsfunksjonen (), og den sletter elementet fra forsiden av køen som tilfeldigvis er det minste elementet.

Igjen kaller vi “remove ()” -funksjonen som fjerner elementet som er angitt som en parameter fra køen. Vi bruker også funksjonen 'Inneholder ()' for å sjekke om et bestemt element er tilstede i køen. Til slutt konverterer vi køen til et arrayobjekt ved hjelp av “toArray ()” - funksjonen.

applikasjon

  • Lastbalanserings- og avbruddshåndterere i operativsystemet: Operativsystemfunksjoner som lastbalansering og avbruddshåndtering implementeres ved hjelp av prioritetskøer. Lastbalanseringsaktiviteten planlegger ressursene med høyest prioritet for effektivt å kunne bære lastbalanseringen. Avbruddshåndtering utføres ved å betjene avbruddene med høyest prioritet. Denne funksjonaliteten kan implementeres effektivt ved hjelp av prioritetskøene.
  • Rute: Routing er en funksjon som brukes til å dirigere nettverksressursene slik at vi får maksimal gjennomstrømning med minimum behandlingstid. Dette kan også implementeres ved hjelp av prioritetskøen.
  • Sykehusberedskap: På et sykehus beredskapsrom blir pasientene deltatt i henhold til hvor alvorlig pasientens tilstand er. Dette kan simuleres ved hjelp av prioritetskøer.
  • Dijkstras korteste sti-algoritme: Her lagres grafen som en nærhetsliste, og vi kan bruke en prioritetskø for å hente ut den minste vektede kanten effektivt fra nærhetslisten for å implementere Dijkstras korteste banealgoritme.
  • Prioritetskø kan også brukes til å lagre nøkkelnøkler og trekke ut minimumnøkkelnoden mens du implementerer spennende tre.

Konklusjon

Prioritetskøer er bare forlengelsen av køen. Men i motsetning til køer som legger til / fjerner elementer ved hjelp av FIFO-tilnærmingen, fjernes elementene i køen i henhold til prioriteten i prioritetskø. Dermed er hvert element i køen assosiert med en prioritet, og varen med høyest prioritet er den første som blir tatt av køen.

Prioritetskøen har tre hovedoperasjoner, dvs. sett inn (), getHighestPriority () og deleteHighestPriority (). Prioritetskø kan implementeres ved hjelp av arrays eller koblet liste, men arbeidet er ikke veldig effektivt. Prioritetskø kan også implementeres ved hjelp av dynger, og ytelsen er mye raskere.

I C ++ har vi også en containerklasse som implementerer funksjonaliteten til en prioritetskø. I Java er det en innebygd klasse Priority_queue som gir funksjonaliteten til en prioritetskø.

Prioritetskøen brukes hovedsakelig i applikasjoner som krever at varer behandles i henhold til prioriteten. For eksempel, den brukes i avbrytende håndtering.

Vår kommende veiledning vil utforske alt om sirkulær kø som er enda en utvidelse av køen.

=> Besøk her for hele C ++ kurset fra eksperter.

Anbefalt lesing

^