Menu

Prioriteitswachtrijgegevensstructuur in C ++ met illustratie

  • Hoofd
  • Andere
  • Prioriteitswachtrijgegevensstructuur in C ++ met illustratie

priority queue data structure c with illustration

Probeer Ons Instrument Voor Het Oplossen Van Problemen

Inleiding tot prioriteitswachtrij in C ++ met illustratie.

Priority Queue is een uitbreiding van de wachtrij die we in onze laatste tutorial hebben besproken.

Het lijkt in bepaalde opzichten op de wachtrij, maar verschilt op de volgende punten van de gewone wachtrij:

  • Elk item in de prioriteitswachtrij is gekoppeld aan een prioriteit.
  • Het item met de hoogste prioriteit is het eerste item dat uit de wachtrij wordt verwijderd.
  • Als meer dan één item dezelfde prioriteit heeft, wordt hun volgorde in de wachtrij in aanmerking genomen.

​ Klik hier voor de Absolute C ++ trainingsserie.

Prioriteitswachtrij in C ++

We kunnen de prioriteitswachtrij visualiseren als een aangepaste versie van de wachtrij, behalve dat wanneer het item uit de wachtrij moet worden gehaald, het item met de hoogste prioriteit als eerste wordt opgehaald. Daarom geven we er de voorkeur aan om de prioriteitswachtrijen te gebruiken in plaats van de wachtrijen wanneer we de items op basis van prioriteit moeten verwerken.

Wat je leert:

Basisbewerkingen

Laten we enkele basisbewerkingen bespreken die worden ondersteund door de prioriteitswachtrij.

  • Invoegen (item, prioriteit): Voegt een item met een bepaalde prioriteit in de prioriteitswachtrij in.
  • getHighestPriority (): Retourneert een item met de hoogste prioriteit.
  • deleteHighestPriority (): Verwijdert een item met de hoogste prioriteit.

Afgezien van de bovenstaande bewerkingen, kunnen we ook de normale wachtrijbewerkingen gebruiken, zoals isEmpty (), isFull () en peek ().

Illustratie

Laten we een illustratie bekijken van de prioriteitswachtrij. Voor de eenvoud zullen we ASCII-tekens gebruiken als items in de prioriteitswachtrij. Hoe hoger de ASCII-waarde, hoe hoger de prioriteit.

Begintoestand - Prioriteitswachtrij (PQ) - {} => leeg

illustratie van de prioriteitswachtrij

Uit de bovenstaande illustratie zien we dat de invoegbewerking vergelijkbaar is met een gewone wachtrij. Maar als we de 'deleteHighestPriority' aanroepen voor de prioriteitswachtrij, wordt het element met de hoogste prioriteit eerst verwijderd.

Vandaar dat de eerste keer dat we deze functie aanroepen, item O wordt verwijderd, terwijl de tweede keer item M wordt verwijderd omdat het een hogere prioriteit heeft dan G en A.

Implementatie van prioriteitswachtrijen in C ++

Prioriteitswachtrijen kunnen worden geïmplementeerd met behulp van:

# 1) Arrays / gekoppelde lijsten

We kunnen de prioriteitswachtrijen implementeren met behulp van arrays en dit is de eenvoudigste implementatie voor de prioriteitswachtrijen.

Om de items in de prioriteitswachtrij weer te geven, kunnen we gewoon een struct declareren zoals hieronder:

​

We hebben ook de prioriteit voor elk item aangegeven.

Om een ​​nieuw item in de prioriteitswachtrij in te voegen, hoeven we het item alleen maar aan het einde van de array in te voegen.

Om het element uit de wachtrij te halen met getHighestPriority (), moeten we de array vanaf het begin doorlopen en het item met de hoogste prioriteit retourneren.

Evenzo moeten we, om het item uit de wachtrij te verwijderen met de bewerking deleteHighestPriority, de hele array doorlopen en het item met de hoogste prioriteit verwijderen. Verplaats vervolgens alle andere elementen na het verwijderde item, één positie terug.

We kunnen de prioriteitswachtrij ook implementeren met behulp van een gekoppelde lijst. We kunnen alle bewerkingen op dezelfde manier uitvoeren als arrays. Het enige verschil is dat we de elementen niet hoeven te verplaatsen nadat we deleteHighestPriority hebben aangeroepen.

# 2) Enorm

Het gebruik van heaps om een ​​prioriteitswachtrij te implementeren is de meest efficiënte manier en biedt veel betere prestaties in vergelijking met de gekoppelde lijsten en arrays. In tegenstelling tot de gekoppelde lijst en array, kost heap-implementatie O (logn) tijd voor invoegen en verwijderen van de prioriteitswachtrij. Get operatie, getHighestPriority kost O (1) tijd.

# 3) Ingebouwde prioriteitswachtrij in standaard sjabloonbibliotheek (STL) in C ++

In C ++ hebben we een prioriteitswachtrij als een container-adaptieve klasse, zo ontworpen dat het hoogste element het eerste element in de wachtrij is en alle elementen in aflopende volgorde staan.

Elk item in de prioriteitswachtrij heeft dus een vaste prioriteit.

We hebben klasse in STL, die de implementatie van de prioriteitswachtrij bevat.

De verschillende bewerkingen die worden ondersteund door de prioriteitswachtrij zijn als volgt:

  1. priority_queue :: size (): Retourneert de grootte van de wachtrij.
  2. prioriteit_wachtrij :: leeg (): Controleert of de wachtrij leeg is en geeft de status weer.
  3. priority_queue :: top (): Retourneert een verwijzing naar het bovenste element van de prioriteitswachtrij.
  4. priority_queue :: push (): Voegt een item toe aan het einde van de prioriteitswachtrij.
  5. priority_queue :: pop (): Verwijdert het eerste element uit de prioriteitswachtrij.
  6. priority_queue :: swap (): Wordt gebruikt om de inhoud van de ene prioriteitswachtrij te wisselen met een andere van hetzelfde type en dezelfde grootte.
  7. prioriteitswachtrijwaardetype: Waardetype geeft het type element aan dat is opgeslagen in een prioriteitswachtrij. Dit fungeert ook als synoniem voor de sjabloonparameter.
  8. priority_queue :: emplace (): Wordt gebruikt om een ​​nieuw element in te voegen in de prioriteitswachtrijcontainer bovenaan de wachtrij.

In het volgende programma zullen we de functionaliteit van de prioriteitswachtrij in STL in C ++ zien.

​

Uitgang:

toepassingen van java in de echte wereld

Grootte van de wachtrij (pq.size ()): 5
Topelement van de wachtrij (pq.top ()): 9
De prioriteit wachtrij pq is: 9 7 5 3 1
Prioriteitswachtrij, na pq.pop () bewerking: 7 5 3 1

Java-implementatie voor prioriteitswachtrij

Prioriteitswachtrij in Java is een speciale wachtrij waar alle elementen in de wachtrij worden geordend volgens natuurlijke ordening of aangepaste volgorde met behulp van een comparator die bij de wachtrij wordt geleverd.

Een prioriteitswachtrij in Java ziet er uit zoals hieronder weergegeven:

Java-implementatie voor prioriteitswachtrij

In de Java-prioriteitswachtrij zijn de elementen zo gerangschikt dat het minste element vooraan in de wachtrij staat en het grootste element achteraan de wachtrij. Dus als we het element uit de prioriteitswachtrij verwijderen, wordt altijd het kleinste element verwijderd.

De klasse die de prioriteitswachtrij in Java implementeert, is 'PriorityQueue' en maakt deel uit van het verzamelingsraamwerk van Java. Het implementeert de 'Queue' -interface van Java.

Hieronder volgt de klassenhiërarchie voor de Java PriorityQueue-klasse.

klassehiërarchie voor Java PriorityQueue-klasse

Hieronder wordt een voorbeeld gegeven van de functionaliteit van de prioriteitswachtrij met gehele getallen als items in Java.

​

Uitgang:

peek () :: Head waarde: 1
De prioriteitswachtrij:
1 3 5 7
Na poll () functie, prioriteitswachtrij:
3 7 5
Na de functie Verwijderen (5), prioriteitswachtrij:
3 7
Prioriteitswachtrij bevat 3 ?: waar
Array-elementen:
Waarde: 3
Waarde: 7

In het bovenstaande programma maken we gebruik van de PriorityQueue-klasse van Java om een ​​object van PriorityQueue te maken dat een Integer-object bevat. We voegen elementen toe aan de wachtrij met behulp van de 'add' -functie. Vervolgens wordt de functie poll () aangeroepen en wordt het element van de voorkant van de wachtrij verwijderd dat toevallig het minste element is.

We noemen opnieuw de functie “remove ()” die het element dat als parameter is opgegeven uit de wachtrij verwijdert. We gebruiken ook de functie “Contains ()” om te controleren of een bepaald element aanwezig is in de wachtrij. Ten slotte zetten we de wachtrij om in een array-object met behulp van de functie 'toArray ()'.

Toepassing

  • Besturingssysteem load balancing en interrupt handlers: Besturingssysteemfuncties zoals taakverdeling en afhandeling van interrupts worden geïmplementeerd met behulp van prioriteitswachtrijen. De taakverdelingsactiviteit plant de resources met de hoogste prioriteit om onze taakverdeling effectief uit te voeren. De afhandeling van onderbrekingen wordt uitgevoerd door de onderbrekingen met de hoogste prioriteit te onderhouden. Deze functionaliteit kan effectief worden geïmplementeerd met behulp van de prioriteitswachtrijen.
  • Routing: Routing is een functie die wordt gebruikt om de netwerkbronnen te routeren, zodat we een maximale doorvoer krijgen met een minimale doorlooptijd. Dit kan ook worden geïmplementeerd met behulp van de prioriteitswachtrij.
  • Ziekenhuis Emergency: In een spoedafdeling van een ziekenhuis worden de patiënten verzorgd op basis van hoe ernstig de toestand van de patiënt is. Dit kan worden gesimuleerd met behulp van prioriteitswachtrijen.
  • Dijkstra's kortste pad-algoritme: Hier wordt de grafiek opgeslagen als een aangrenzende lijst en kunnen we een prioriteitswachtrij gebruiken om de minimaal gewogen rand efficiënt uit de aangrenzende lijst te halen om Dijkstra's kortste pad-algoritme te implementeren.
  • Prioriteitswachtrij kan ook worden gebruikt om knooppuntsleutels op te slaan en het minimale sleutelknooppunt te extraheren tijdens het implementeren van spanning tree.

Gevolgtrekking

Prioriteitswachtrijen zijn niets anders dan het verlengstuk van de wachtrij. Maar in tegenstelling tot wachtrijen die items toevoegen / verwijderen met behulp van de FIFO-benadering, worden in de prioriteitswachtrij de items verwijderd uit de wachtrij op basis van de prioriteit. Elk item in de wachtrij krijgt dus een prioriteit en het item met de hoogste prioriteit is het eerste dat uit de wachtrij wordt gehaald.

De prioriteitswachtrij heeft drie hoofdbewerkingen, namelijk insert (), getHighestPriority () en deleteHighestPriority (). Prioriteitswachtrij kan worden geïmplementeerd met behulp van arrays of gekoppelde lijsten, maar de werking is niet erg efficiënt. Prioriteitswachtrij kan ook worden geïmplementeerd met behulp van hopen en de prestaties zijn veel sneller.

In C ++ hebben we ook een containerklasse die de functionaliteit van een prioriteitswachtrij implementeert. In Java is er een ingebouwde class priority_queue die de functionaliteit van een prioriteitswachtrij biedt.

De prioriteitswachtrij wordt voornamelijk gebruikt in toepassingen waarbij items moeten worden verwerkt volgens de prioriteit. Bijvoorbeeld, het wordt gebruikt bij het afhandelen van onderbrekingen.

Onze aanstaande tutorial zal alles verkennen over de circulaire wachtrij, die nog een ander verlengstuk van de wachtrij is.

​ Bezoek hier voor de complete C ++ -cursus van experts.

Aanbevolen literatuur

^