Menu

Prioriteret kø datastruktur i C ++ med illustration

priority queue data structure c with illustration

Prøv Vores Instrument Til At Fjerne Problemer

Introduktion til prioritetskø i C ++ med illustration.

Priority Queue er en udvidelse af køen, som vi diskuterede i vores sidste tutorial.

Det ligner køen i visse aspekter, og alligevel adskiller den sig fra den almindelige kø i følgende punkter:

  • Hvert element i prioritetskøen er knyttet til en prioritet.
  • Emnet med den højeste prioritet er det første element, der fjernes fra køen.
  • Hvis mere end en vare har samme prioritet, overvejes deres rækkefølge i køen.

=> Klik her for den absolutte C ++ træningsserie.

Prioritetskø i C ++

Vi kan visualisere prioritetskøen som en ændret version af køen, bortset fra at når varen skal tages ud af køen, hentes emnet med den højeste prioritet først. Så vi foretrækker at bruge prioritetskøerne i stedet for køerne, når vi har brug for at behandle elementerne baseret på prioritet.

Hvad du lærer:

Grundlæggende funktioner

Lad os diskutere nogle af de grundlæggende operationer understøttet af prioritetskøen.

  • Indsæt (emne, prioritet): Indsætter et element i prioritetskøen med en given prioritet.
  • getHighestPriority (): Returnerer et element med den højeste prioritet.
  • deleteHighestPriority (): Fjerner et element med den højeste prioritet.

Bortset fra ovenstående operationer kan vi også bruge de normale køoperationer som isEmpty (), isFull () og peek ().

Illustration

Lad os se en illustration af prioritetskøen. For enkelheds skyld vil vi bruge ASCII-tegn som emner i prioritetskøen. Jo højere ASCII-værdi, jo højere er prioriteten.

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

illustration af prioritetskøen

Fra ovenstående illustration ser vi, at indsætningsoperationen ligner en almindelig kø. Men når vi kalder “deleteHighestPriority” for prioritetskøen, fjernes elementet med den højeste prioritet først.

Derfor fjernes element O første gang, når vi kalder denne funktion, mens anden gang fjernes elementet M, da det har højere prioritet end G og A.

Implementering af prioritetskøer i C ++

Prioriterede køer kan implementeres ved hjælp af:

# 1) Arrays / Tilknyttede lister

Vi kan implementere prioritetskøerne ved hjælp af arrays, og dette er den enkleste implementering af prioritetskøerne.

For at repræsentere elementerne i prioritetskøen kan vi bare erklære en struktur som nedenfor:

struct pq_item{ int item; int priority; };

Vi har også erklæret prioriteten for hver vare.

For at indsætte et nyt element i prioritetskøen skal vi blot indsætte elementet i slutningen af ​​arrayet.

For at få elementet fra køen ved hjælp af getHighestPriority (), er vi nødt til at krydse arrayet fra starten og returnere elementet med den højeste prioritet.

På samme måde er det nødvendigt at krydse hele arrayet og slette elementet med den højeste prioritet for at fjerne elementet fra køen ved hjælp af deleteHighestPriority-operationen. Flyt derefter alle de andre elementer efter det slettede element, en position tilbage.

Vi kan også implementere prioritetskøen ved hjælp af en linket liste. Vi kan udføre alle operationer på samme måde som arrays. Den eneste forskel er, at vi ikke behøver at flytte elementerne efter at have kaldt deleteHighestPriority.

# 2) dynger

Brug af dynger til at implementere en prioritetskø er den mest effektive måde, og det giver meget bedre ydeevne sammenlignet med de sammenkædede lister og arrays. I modsætning til den sammenkædede liste og matrix tager bunkeimplementering O (logn) tid til indsættelse og sletning af prioritetskøen. Få operation, getHighestPriority tager O (1) tid.

# 3) Indbygget prioritetskø i standardskabelonbiblioteket (STL) i C ++

I C ++ har vi en prioritetskø som en containeradaptiv klasse, designet på en sådan måde, at det højeste element er det første element i køen, og alle elementerne er i faldende rækkefølge.

Således har hvert element i prioritetskøen en fast prioritet.

Vi har klasse i STL, som indeholder prioritetskøimplementering.

De forskellige operationer, der understøttes af prioritetskøen, er som følger:

  1. prioritering_størrelse :: størrelse (): Returnerer køens størrelse.
  2. prioritetsvægt :: tom (): Kontrollerer, om køen er tom og returnerer sin status.
  3. prioritets_køb :: top (): Returnerer en henvisning til det øverste element i prioritetskøen.
  4. prioritering_skue :: skub (): Tilføjer et element i slutningen af ​​prioritetskøen.
  5. prioritetsvinkel :: pop (): Fjerner det første element fra prioritetskøen.
  6. prioritetsvægt :: bytte (): Bruges til at bytte indholdet af en prioritetskø med en anden af ​​samme type og størrelse.
  7. prioritet kø værdi værdi: Værditype giver typen af ​​elementet, der er gemt i en prioritetskø. Dette fungerer også som et synonym for skabelonparameteren.
  8. prioritets_køb :: emplace (): Bruges til at indsætte et nyt element i beholderen til prioritetskø øverst i køen.

I det næste program vil vi se funktionaliteten i 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; }

Produktion:

team foundation server agil projektledelse

Køens størrelse (pq.størrelse ()): 5
Det øverste element i køen (pq.top ()): 9
Prioritetskøen pq er: 9 7 5 3 1
Prioritetskø efter pq.pop () -operation: 7 5 3 1

Java-implementering til prioritetskø

Prioritetskø i java er en speciel kø, hvor alle elementerne i køen bestilles i henhold til naturlig bestilling eller brugerdefineret rækkefølge ved hjælp af en komparator, der følger med køen.

En prioritetskø i Java ser ud som vist nedenfor:

Java-implementering til prioritetskø

I Java-prioritetskø er elementerne arrangeret således, at det mindste element er forrest i køen, og det største element er bagest i køen. Så når vi fjerner elementet fra prioritetskøen, er det altid det mindste element, der fjernes.

Klassen, der implementerer prioritetskøen i Java, er 'PriorityQueue' og er en del af Java-samlingsrammen. Det implementerer 'Kø' -grænsefladen på Java.

Følgende er klassehierarkiet for Java PriorityQueue-klassen.

klassehierarki for Java PriorityQueue-klasse

Nedenfor er et eksempel på prioritetskøfunktionalitet med heltal 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

Produktion:

peek () :: Hovedværdi: 1
Prioritetskøen:
1 3 5 7
Funktion efter afstemning (), prioritetskø:
3 7 5
Efter Fjern (5) -funktion, prioritetskø:
3 7
Prioritetskø indeholder 3 ?: sand
Matrixelementer:
Værdi: 3
Værdi: 7

I ovenstående program bruger vi PriorityQueue-klassen i Java til at oprette et objekt af PriorityQueue, der indeholder et heltal-objekt. Vi tilføjer elementer i køen ved hjælp af 'tilføj' -funktionen. Derefter kaldes afstemningsfunktionen (), og den sletter elementet fra forsiden af ​​køen, hvilket tilfældigvis er det mindste element.

Igen kalder vi funktionen “remove ()”, der fjerner det element, der er angivet som en parameter fra køen. Vi bruger også funktionen 'Indeholder ()' til at kontrollere, om et bestemt element er til stede i køen. Endelig konverterer vi køen til et array-objekt ved hjælp af funktionen 'toArray ()'.

Ansøgning

  • Operativsystemets belastningsbalancering og afbrydere: Operativsystemfunktioner som belastningsbalancering og afbrydelse af håndtering implementeres ved hjælp af prioritetskøer. Belastningsbalanceringsaktiviteten planlægger ressourcerne med den højeste prioritet for effektivt at kunne bære vores belastningsafbalancering. Afbrydelse håndteres ved at servicere afbrydelserne med den højeste prioritet. Denne funktionalitet kan implementeres effektivt ved hjælp af prioritetskøerne.
  • Routing: Routing er en funktion, der bruges til at dirigere netværksressourcerne, så vi får maksimal gennemstrømning med minimal leveringstid. Dette kan også implementeres ved hjælp af prioritetskøen.
  • Hospital akut: På et akutrum på hospitalet overværes patienterne i henhold til hvor alvorlig patientens tilstand er. Dette kan simuleres ved hjælp af prioritetskøer.
  • Dijkstras korteste sti-algoritme: Her er grafen gemt som en nærhedsliste, og vi kan bruge en prioritetskø til at udtrække den mindste vægtede kant effektivt fra nærhedslisten for at implementere Dijkstras korteste sti-algoritme.
  • Prioritetskø kan også bruges til at gemme nodenøgler og udtrække den mindste nøglenode, mens der implementeres spændende træ.

Konklusion

Prioriterede køer er kun udvidelsen af ​​køen. Men i modsætning til køer, der tilføjer / fjerner emner ved hjælp af FIFO-tilgangen, fjernes emnerne i prioritetskøen fra køen i henhold til prioriteten. Således er hvert element i køen forbundet med en prioritet, og det element med den højeste prioritet er det første, der tages ud af køen.

Prioritetskøen har tre hovedoperationer, dvs. indsæt (), getHighestPriority () og deleteHighestPriority (). Prioritetskø kan implementeres ved hjælp af arrays eller en sammenkædet liste, men arbejdet er ikke meget effektivt. Prioritetskø kan også implementeres ved hjælp af dynger, og ydeevnen er meget hurtigere.

I C ++ har vi også en containerklasse, der implementerer funktionaliteten i en prioritetskø. I Java er der en indbygget klasse Priority_queue, der giver funktionaliteten i en prioritetskø.

Prioritetskøen bruges hovedsageligt i applikationer, der kræver, at varer behandles i henhold til prioriteten. For eksempel, det bruges til afbrydelse af håndtering.

Vores kommende vejledning vil udforske alt om cirkulær kø, som er endnu en udvidelse af køen.

=> Besøg her for det komplette C ++ kursus fra eksperter.

Anbefalet læsning

^