priority queue data structure c with illustration
Introduktion till prioriterad kö i C ++ med illustration.
Priority Queue är en förlängning av kön som vi diskuterade i vår senaste handledning.
Det liknar kön i vissa aspekter och ändå skiljer det sig från den vanliga köen i följande punkter:
- Varje objekt i prioritetskön är associerat med en prioritet.
- Objektet med högsta prioritet är det första objektet som tas bort från kön.
- Om mer än ett objekt har samma prioritet övervägs deras ordning i kön.
=> Klicka här för den absoluta C ++ träningsserien.
Vi kan visualisera prioritetskön som en modifierad version av kön förutom att när objektet ska tas bort från kön, hämtas objektet med högsta prioritet först. Så vi föredrar att använda prioritetsköerna istället för köerna när vi behöver bearbeta objekten baserat på prioritet.
Vad du kommer att lära dig:
- Grundläggande funktioner
- Illustration
- Implementering av prioritetsköer i C ++
- Ansökan
- Slutsats
- Rekommenderad läsning
Grundläggande funktioner
Låt oss diskutera några av de grundläggande operationerna som stöds av prioritetskön.
- Infoga (objekt, prioritet): Infogar ett objekt i prioritetskön med en given prioritet.
- getHighestPriority (): Returnerar ett objekt med högsta prioritet.
- deleteHighestPriority (): Tar bort ett objekt med högsta prioritet.
Förutom ovanstående operationer kan vi också använda de normala köåtgärderna som isEmpty (), isFull () och peek ().
Illustration
Låt oss se en illustration av prioritetskön. För enkelhets skull använder vi ASCII-tecken som objekt i prioritetskön. Ju högre ASCII-värde, desto högre prioritet.
Ursprungligt tillstånd - Prioritetskö (PQ) - {} => tom
Från ovanstående illustration ser vi att insättningsoperationen liknar en vanlig kö. Men när vi kallar 'deleteHighestPriority' för prioritetskön tas elementet med högsta prioritet bort först.
Därav första gången när vi kallar denna funktion tas objekt O bort medan andra gången tas objekt M bort eftersom det har högre prioritet än G och A.
Implementering av prioritetsköer i C ++
Prioriterade köer kan implementeras med:
# 1) Arrayer / länkade listor
Vi kan implementera prioritetsköerna med hjälp av arrays och detta är den enklaste implementeringen för prioritetsköerna.
För att representera objekten i prioritetskön kan vi bara förklara en struktur enligt nedan:
struct pq_item{ int item; int priority; };Vi har också förklarat prioriteten för varje artikel.
För att infoga ett nytt objekt i prioritetskön måste vi helt enkelt infoga objektet i slutet av matrisen.
För att få elementet från kön med getHighestPriority (), måste vi korsa arrayen från början och returnera artikeln med högsta prioritet.
På samma sätt, för att ta bort objektet från kön med deleteHighestPriority-operationen, måste vi korsa hela matrisen och ta bort objektet med högsta prioritet. Flytta sedan alla andra element efter det raderade objektet, en position tillbaka.
Vi kan också implementera prioritetskön med hjälp av en länkad lista. Vi kan utföra alla operationer på liknande sätt som arrays. Den enda skillnaden är att vi inte behöver flytta elementen efter att ha ringt deleteHighestPriority.
# 2) Högar
Att använda högar för att implementera en prioritetskö är det mest effektiva sättet och det ger mycket bättre prestanda jämfört med länkade listor och matriser. I motsats till den länkade listan och arrayen tar heapimplementering O (logn) tid för att infoga och ta bort operationer i prioritetskön. Få operation, getHighestPriority tar O (1) tid.
# 3) Inbyggd prioritetskö i standardmallbiblioteket (STL) i C ++
I C ++ har vi en prioritetskö som en containeradaptiv klass, utformad på ett sådant sätt att det högsta elementet är det första elementet i kön och alla element är i minskande ordning.
Således har varje objekt i prioritetskön en fast prioritet.
Vi har klass i STL, som innehåller prioritetsköimplementering.
De olika operationerna som stöds av prioritetskön är följande:
- prioritets_kö :: storlek (): Returnerar storleken på kön.
- prioritets_kö :: tom (): Kontrollerar om kön är tom och returnerar sin status.
- prioritets_kö :: top (): Returnerar en referens till det översta elementet i prioritetskön.
- prioritets_kö :: push (): Lägger till ett objekt i slutet av prioritetskön.
- prioritets_kö :: pop (): Tar bort det första elementet från prioritetskön.
- prioritets_kö :: byta (): Används för att byta innehållet i en prioritetskö med en annan av samma typ och storlek.
- prioritetstyp för kövärde: Värdetyp ger typen av element som lagras i en prioritetskö. Detta fungerar också som en synonym för mallparametern.
- prioritets_kö :: emplace (): Används för att infoga ett nytt element i behållaren för prioritetskön högst upp i kön.
I nästa program ser vi funktionaliteten i prioritetskön 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:
hur man startar ett java-projekt
Köns storlek (pq.storlek ()): 5
Köns översta element (pq.top ()): 9
Prioritetskön pq är: 9 7 5 3 1
Prioritetskö, efter pq.pop () -åtgärd: 7 5 3 1
Java-implementering för prioritetskö
Prioritetskö i java är en speciell kö där alla element i kön ordnas enligt naturlig beställning eller anpassad beställning med hjälp av en komparator som medföljer kön.
En prioritetskö i Java ser ut som visas nedan:
I Java-prioritetskö är elementen ordnade så att det minsta elementet är längst fram i kön och det största elementet är längst bak i kön. Så när vi tar bort elementet från prioritetskön är det alltid det minsta elementet som tas bort.
Klassen som implementerar prioritetskön i Java är 'PriorityQueue' och är en del av Java-samlingsramen. Den implementerar Java-gränssnittet 'Kö'.
Följande är klasshierarkin för Java PriorityQueue-klassen.
Nedan följer ett exempel på Priority Queue-funktionalitet med heltal som objekt 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 () :: Huvudvärde: 1
Prioritetskön:
1 3 5 7
After poll () -funktion, prioritetskö:
3 7 5
Efter funktionen Ta bort (5), prioritetskö:
3 7
Prioritetskön innehåller 3 ?: sant
Array element:
Värde: 3
Värde: 7
I ovanstående program använder vi klassen PriorityQueue på Java för att skapa ett objekt av PriorityQueue som innehåller ett heltal-objekt. Vi lägger till element i kön med funktionen 'lägg till'. Sedan kallas funktionen poll () och den raderar elementet från kön fram, vilket råkar vara det minsta elementet.
Återigen kallar vi “ta bort ()” -funktionen som tar bort elementet som anges som en parameter från kön. Vi använder också funktionen 'Innehåller ()' för att kontrollera om ett visst element finns i kön. Slutligen konverterar vi kön till ett arrayobjekt med funktionen “toArray ()”.
Ansökan
- Operativsystems lastbalanserings- och avbrottshanterare: Operativsystemfunktioner som lastbalansering och avbrottshantering implementeras med prioritetsköer. Lastbalanseringsaktiviteten schemalägger resurserna med högsta prioritet för att effektivt genomföra vår lastbalansering. Avbrottshantering utförs genom att underhålla avbrotten med högsta prioritet. Denna funktionalitet kan implementeras effektivt med hjälp av prioritetsköerna.
- Rutt: Routing är en funktion som används för att dirigera nätverksresurserna så att vi får maximal genomströmning med minimal omloppstid. Detta kan också implementeras med prioritetskön.
- Sjukhus akut: I ett akutmottagning på sjukhus besöks patienterna efter hur svårt patientens tillstånd är. Detta kan simuleras med prioritetsköer.
- Dijkstras algoritm för kortaste vägen: Här lagras diagrammet som en angränsningslista och vi kan använda en prioritetskö för att extrahera den minsta viktade kanten effektivt från angränsningslistan för att implementera Dijkstras kortaste algoritm.
- Prioriteringskön kan också användas för att lagra nodnycklar och extrahera minsta nyckelnoden medan du implementerar spännande träd.
Slutsats
Prioriterade köer är inget annat än förlängningen av kön. Men till skillnad från köer som lägger till / tar bort objekt med hjälp av FIFO-metoden, i prioritetskön tas objekten bort från kön enligt prioriteten. Således är varje objekt i kön associerat med en prioritet och objektet med högsta prioritet är det första som tas bort från kön.
Prioritetskön har tre huvudåtgärder, dvs insert (), getHighestPriority () och deleteHighestPriority (). Prioritetskön kan implementeras med hjälp av arrays eller länkad lista men arbetet är inte särskilt effektivt. Prioritetskön kan också implementeras med massor och prestanda är mycket snabbare.
I C ++ har vi också en behållarklass som implementerar funktionaliteten i en prioritetskö. I Java finns en inbyggd klass Priority_queue som ger funktionaliteten i en prioritetskö.
Prioritetskön används främst i applikationer som kräver att objekt bearbetas enligt prioriteten. Till exempel, den används vid avbrottshantering.
Vår kommande handledning kommer att utforska allt om cirkulär kö som är ytterligare en förlängning av kön.
=> Besök här för en komplett C ++ - kurs från experter.
Rekommenderad läsning
- Kodatastruktur i C ++ med illustration
- Prioritetskö i STL
- Stack datastruktur i C ++ med illustration
- Cirkulär länkad datastruktur i C ++ med illustration
- Länkad listdatastruktur i C ++ med illustration
- Dubbelt länkad datastruktur i C ++ med illustration
- Introduktion till datastrukturer i C ++
- Så här testar du programmeddelandekön: IBM WebSphere MQ Intro Tutorial