A prioriteits-rij is een type wachtrij dat elementen rangschikt op basis van hun prioriteitswaarden. Elementen met hogere prioriteitswaarden worden doorgaans opgehaald vóór elementen met lagere prioriteitswaarden.
In een prioriteitswachtrij is aan elk element een prioriteitswaarde gekoppeld. Wanneer u een element aan de wachtrij toevoegt, wordt het ingevoegd op een positie op basis van de prioriteitswaarde ervan. Als u bijvoorbeeld een element met een hoge prioriteitswaarde aan een prioriteitswachtrij toevoegt, kan dit aan de voorkant van de wachtrij worden ingevoegd, terwijl een element met een lage prioriteitswaarde aan de achterkant kan worden ingevoegd.
Er zijn verschillende manieren om een prioriteitswachtrij te implementeren, waaronder het gebruik van een array, gekoppelde lijst, heap of binaire zoekboom. Elke methode heeft zijn eigen voor- en nadelen, en de beste keuze zal afhangen van de specifieke behoeften van uw toepassing.
Prioriteitswachtrijen worden vaak gebruikt in realtime systemen, waarbij de volgorde waarin elementen worden verwerkt aanzienlijke gevolgen kan hebben. Ze worden ook gebruikt in algoritmen om hun efficiëntie te verbeteren, zoals Het algoritme van Dijkstra voor het vinden van het kortste pad in een grafiek en het A*-zoekalgoritme voor het vinden van paden.
Eigenschappen van prioriteitswachtrij
Een prioriteitswachtrij is dus een uitbreiding van de wachtrij met de volgende eigenschappen.
- Aan elk item is een prioriteit verbonden.
- Een element met hoge prioriteit wordt uit de wachtrij gehaald vóór een element met lage prioriteit.
- Als twee elementen dezelfde prioriteit hebben, worden ze geserveerd volgens hun volgorde in de wachtrij.
In de onderstaande prioriteitswachtrij heeft een element met een maximale ASCII-waarde de hoogste prioriteit. De elementen met een hogere prioriteit worden als eerste bediend.
Hoe wordt prioriteit toegewezen aan de elementen in een prioriteitswachtrij?
In een prioriteitswachtrij wordt doorgaans rekening gehouden met de waarde van een element voor het toekennen van de prioriteit.
Het element met de hoogste waarde krijgt bijvoorbeeld de hoogste prioriteit en het element met de laagste waarde krijgt de laagste prioriteit. Het omgekeerde geval kan ook worden gebruikt, dat wil zeggen dat aan het element met de laagste waarde de hoogste prioriteit kan worden toegewezen. Ook kan de prioriteit worden toegewezen op basis van onze behoeften.
Bewerkingen van een prioriteitswachtrij:
Een typische prioriteitswachtrij ondersteunt de volgende bewerkingen:
1) Invoeging in een prioriteitswachtrij
Wanneer een nieuw element in een prioriteitswachtrij wordt ingevoegd, wordt het van boven naar beneden en van links naar rechts naar het lege slot verplaatst. Als het element zich echter niet op de juiste plaats bevindt, wordt het vergeleken met het bovenliggende knooppunt. Als het element niet in de juiste volgorde staat, worden de elementen verwisseld. Het verwisselproces gaat door totdat alle elementen op de juiste positie zijn geplaatst.
2) Verwijdering in een prioriteitswachtrij
Zoals je weet is het maximale element in een maximale heap het rootknooppunt. En het zal eerst het element verwijderen dat de maximale prioriteit heeft. U verwijdert dus het hoofdknooppunt uit de wachtrij. Door deze verwijdering ontstaat een leeg slot, dat verder wordt opgevuld met een nieuwe invoeging. Vervolgens vergelijkt het het nieuw ingevoegde element met alle elementen in de wachtrij om de heap invariant te houden.
3) Neem een kijkje in een prioriteitswachtrij
Deze bewerking helpt bij het retourneren van het maximale element uit Max Heap of het minimale element uit Min Heap zonder het knooppunt uit de prioriteitswachtrij te verwijderen.
Soorten prioriteitswachtrijen:
1) Prioriteitswachtrij voor oplopende volgorde
Zoals de naam al doet vermoeden, krijgt in de prioriteitswachtrij met oplopende volgorde het element met een lagere prioriteitswaarde een hogere prioriteit in de prioriteitenlijst. Als we bijvoorbeeld de volgende elementen in een prioriteitswachtrij hebben, gerangschikt in oplopende volgorde, zoals 4,6,8,9,10. Hier is 4 het kleinste getal. Daarom krijgt het de hoogste prioriteit in een prioriteitswachtrij. Als we dus uit de wachtrij van dit type prioriteitswachtrij stappen, wordt 4 uit de wachtrij verwijderd en retourneert de wachtrij 4.
2) Aflopende volgorde Prioriteitswachtrij
Het rootknooppunt is het maximale element in een maximale heap, zoals u wellicht weet. Het zal ook eerst het element met de hoogste prioriteit verwijderen. Als gevolg hiervan wordt het hoofdknooppunt uit de wachtrij verwijderd. Deze verwijdering laat een lege ruimte achter, die in de toekomst zal worden opgevuld met nieuwe toevoegingen. De heap-invariant wordt vervolgens gehandhaafd door het nieuw ingevoegde element te vergelijken met alle andere vermeldingen in de wachtrij.
Soorten prioriteitswachtrijen
Verschil tussen prioriteitswachtrij en normale wachtrij?
Er is geen prioriteit verbonden aan elementen in een wachtrij; de regel van first-in-first-out (FIFO) is geïmplementeerd, terwijl in een prioriteitswachtrij de elementen een prioriteit hebben. De elementen met een hogere prioriteit worden als eerste bediend.
Hoe Prioriteitswachtrij implementeren?
Prioriteitswachtrij kan worden geïmplementeerd met behulp van de volgende datastructuren:
- Arrays
- Gekoppelde lijst
- Heap-gegevensstructuur
- Binaire zoekboom
Laten we dit allemaal in detail bespreken.
1) Prioriteitswachtrij implementeren met behulp van array:
Een eenvoudige implementatie is het gebruik van een array met de volgende structuur.
structuuritem {
int-item;
int-prioriteit;
}
- enqueue(): Deze functie wordt gebruikt om nieuwe gegevens in de wachtrij in te voegen. dequeue(): Deze functie verwijdert het element met de hoogste prioriteit uit de wachtrij. peek()/top(): Deze functie wordt gebruikt om het element met de hoogste prioriteit in de wachtrij te krijgen zonder het uit de wachtrij te verwijderen.
| Arrays | in de wachtrij plaatsen() | overeenkomstig () | kijkje() |
|---|---|---|---|
| Tijdcomplexiteit | O(1) | Op) | Op) |
C++
// C++ program to implement Priority Queue> // using Arrays> #include> using> namespace> std;> // Structure for the elements in the> // priority queue> struct> item {> >int> value;> >int> priority;> };> // Store the element of a priority queue> item pr[100000];> // Pointer to the last index> int> size = -1;> // Function to insert a new element> // into priority queue> void> enqueue(>int> value,>int> priority)> {> >// Increase the size> >size++;> >// Insert the element> >pr[size].value = value;> >pr[size].priority = priority;> }> // Function to check the top element> int> peek()> {> >int> highestPriority = INT_MIN;> >int> ind = -1;> >// Check for the element with> >// highest priority> >for> (>int> i = 0; i <= size; i++) {> >// If priority is same choose> >// the element with the> >// highest value> >if> (highestPriority == pr[i].priority && ind>-1> >&& pr[ind].value highestPriority = pr[i].priority; ind = i; } else if (highestPriority highestPriority = pr[i].priority; ind = i; } } // Return position of the element return ind; } // Function to remove the element with // the highest priority void dequeue() { // Find the position of the element // with highest priority int ind = peek(); // Shift the element one index before // from the position of the element // with highest priority is found for (int i = ind; i pr[i] = pr[i + 1]; } // Decrease the size of the // priority queue by one size--; } // Driver Code int main() { // Function Call to insert elements // as per the priority enqueue(10, 2); enqueue(14, 4); enqueue(16, 4); enqueue(12, 3); // Stores the top element // at the moment int ind = peek(); cout << pr[ind].value << endl; // Dequeue the top element dequeue(); // Check the top element ind = peek(); cout << pr[ind].value << endl; // Dequeue the top element dequeue(); // Check the top element ind = peek(); cout << pr[ind].value << endl; return 0; }> |
>
>
Java
// Java program to implement Priority Queue> // using Arrays> import> java.util.*;> // Structure for the elements in the> // priority queue> class> item {> >public> int> value;> >public> int> priority;> };> class> GFG {> >// Store the element of a priority queue> >static> item[] pr =>new> item[>100000>];> >// Pointer to the last index> >static> int> size = ->1>;> >// Function to insert a new element> >// into priority queue> >static> void> enqueue(>int> value,>int> priority)> >{> >// Increase the size> >size++;> >// Insert the element> >pr[size] =>new> item();> >pr[size].value = value;> >pr[size].priority = priority;> >}> >// Function to check the top element> >static> int> peek()> >{> >int> highestPriority = Integer.MIN_VALUE;> >int> ind = ->1>;> >// Check for the element with> >// highest priority> >for> (>int> i =>0>; i <= size; i++) {> >// If priority is same choose> >// the element with the> >// highest value> >if> (highestPriority == pr[i].priority> >&& ind>->1> >&& pr[ind].value highestPriority = pr[i].priority; ind = i; } else if (highestPriority highestPriority = pr[i].priority; ind = i; } } // Return position of the element return ind; } // Function to remove the element with // the highest priority static void dequeue() { // Find the position of the element // with highest priority int ind = peek(); // Shift the element one index before // from the position of the element // with highest priority is found for (int i = ind; i pr[i] = pr[i + 1]; } // Decrease the size of the // priority queue by one size--; } public static void main(String[] args) { // Function Call to insert elements // as per the priority enqueue(10, 2); enqueue(14, 4); enqueue(16, 4); enqueue(12, 3); // Stores the top element // at the moment int ind = peek(); System.out.println(pr[ind].value); // Dequeue the top element dequeue(); // Check the top element ind = peek(); System.out.println(pr[ind].value); // Dequeue the top element dequeue(); // Check the top element ind = peek(); System.out.println(pr[ind].value); } } // this code is contributed by phasing17> |
>
>
Python3
import> sys> # Structure for the elements in the> # priority queue> class> item :> >value>=> 0> >priority>=> 0> class> GFG :> > ># Store the element of a priority queue> >pr>=> [>None>]>*> (>100000>)> > ># Pointer to the last index> >size>=> ->1> > ># Function to insert a new element> ># into priority queue> >@staticmethod> >def> enqueue( value, priority) :> > ># Increase the size> >GFG.size>+>=> 1> > ># Insert the element> >GFG.pr[GFG.size]>=> item()> >GFG.pr[GFG.size].value>=> value> >GFG.pr[GFG.size].priority>=> priority> > ># Function to check the top element> >@staticmethod> >def> peek() :> >highestPriority>=> ->sys.maxsize> >ind>=> ->1> > ># Check for the element with> ># highest priority> >i>=> 0> >while> (i <>=> GFG.size) :> > ># If priority is same choose> ># the element with the> ># highest value> >if> (highestPriority>=>=> GFG.pr[i].priority>and> ind>>->1> and> GFG.pr[ind].value highestPriority = GFG.pr[i].priority ind = i elif(highestPriority highestPriority = GFG.pr[i].priority ind = i i += 1 # Return position of the element return ind # Function to remove the element with # the highest priority @staticmethod def dequeue() : # Find the position of the element # with highest priority ind = GFG.peek() # Shift the element one index before # from the position of the element # with highest priority is found i = ind while (i GFG.pr[i] = GFG.pr[i + 1] i += 1 # Decrease the size of the # priority queue by one GFG.size -= 1 @staticmethod def main( args) : # Function Call to insert elements # as per the priority GFG.enqueue(10, 2) GFG.enqueue(14, 4) GFG.enqueue(16, 4) GFG.enqueue(12, 3) # Stores the top element # at the moment ind = GFG.peek() print(GFG.pr[ind].value) # Dequeue the top element GFG.dequeue() # Check the top element ind = GFG.peek() print(GFG.pr[ind].value) # Dequeue the top element GFG.dequeue() # Check the top element ind = GFG.peek() print(GFG.pr[ind].value) if __name__=='__main__': GFG.main([]) # This code is contributed by aadityaburujwale.> |
>
>
C#
// C# program to implement Priority Queue> // using Arrays> using> System;> // Structure for the elements in the> // priority queue> public> class> item {> >public> int> value;> >public> int> priority;> };> public> class> GFG> {> > >// Store the element of a priority queue> >static> item[] pr =>new> item[100000];> >// Pointer to the last index> >static> int> size = -1;> >// Function to insert a new element> >// into priority queue> >static> void> enqueue(>int> value,>int> priority)> >{> >// Increase the size> >size++;> > >// Insert the element> >pr[size] =>new> item();> >pr[size].value = value;> >pr[size].priority = priority;> >}> > >// Function to check the top element> >static> int> peek()> >{> >int> highestPriority =>int>.MinValue;> >int> ind = -1;> > >// Check for the element with> >// highest priority> >for> (>int> i = 0; i <= size; i++) {> > >// If priority is same choose> >// the element with the> >// highest value> >if> (highestPriority == pr[i].priority && ind>-1> >&& pr[ind].value highestPriority = pr[i].priority; ind = i; } else if (highestPriority highestPriority = pr[i].priority; ind = i; } } // Return position of the element return ind; } // Function to remove the element with // the highest priority static void dequeue() { // Find the position of the element // with highest priority int ind = peek(); // Shift the element one index before // from the position of the element // with highest priority is found for (int i = ind; i pr[i] = pr[i + 1]; } // Decrease the size of the // priority queue by one size--; } public static void Main(string[] args) { // Function Call to insert elements // as per the priority enqueue(10, 2); enqueue(14, 4); enqueue(16, 4); enqueue(12, 3); // Stores the top element // at the moment int ind = peek(); Console.WriteLine(pr[ind].value); // Dequeue the top element dequeue(); // Check the top element ind = peek(); Console.WriteLine(pr[ind].value); // Dequeue the top element dequeue(); // Check the top element ind = peek(); Console.WriteLine(pr[ind].value); } } //this code is contributed by phasing17> |
>
>
Javascript
// JavaScript program to implement Priority Queue> // using Arrays> // Structure for the elements in the> // priority queue> class item {> >constructor()> >{> >this>.value;> >this>.priority;> >}> };> // Store the element of a priority queue> let pr = [];> for> (>var> i = 0; i <100000; i++)> >pr.push(>new> item());> // Pointer to the last index> let size = -1;> // Function to insert a new element> // into priority queue> function> enqueue(value, priority)> {> >// Increase the size> >size++;> >// Insert the element> >pr[size] =>new> item();> >pr[size].value = value;> >pr[size].priority = priority;> }> // Function to check the top element> function> peek()> {> >let highestPriority = Number.MIN_SAFE_INTEGER;> >let ind = -1;> >// Check for the element with> >// highest priority> >for> (>var> i = 0; i <= size; i++) {> >// If priority is same choose> >// the element with the> >// highest value> >if> (highestPriority == pr[i].priority && ind>-1> >&& pr[ind].value highestPriority = pr[i].priority; ind = i; } else if (highestPriority highestPriority = pr[i].priority; ind = i; } } // Return position of the element return ind; } // Function to remove the element with // the highest priority function dequeue() { // Find the position of the element // with highest priority let ind = peek(); // Shift the element one index before // from the position of the element // with highest priority is found for (var i = ind; i pr[i] = pr[i + 1]; } // Decrease the size of the // priority queue by one size--; } // Function Call to insert elements // as per the priority enqueue(10, 2); enqueue(14, 4); enqueue(16, 4); enqueue(12, 3); // Stores the top element // at the moment let ind = peek(); console.log(pr[ind].value); // Dequeue the top element dequeue(); // Check the top element ind = peek(); console.log(pr[ind].value); // Dequeue the top element dequeue(); // Check the top element ind = peek(); console.log(pr[ind].value); // this code is contributed by phasing17> |
>
Excel verwijder het eerste teken
>Uitvoer
16 14 12>
Opmerking: Lezen Dit artikel voor meer details.
2) Prioriteitswachtrij implementeren met behulp van een gekoppelde lijst:
In een LinkedList-implementatie worden de vermeldingen in aflopende volgorde gesorteerd op basis van hun prioriteit. Het element met de hoogste prioriteit wordt altijd toegevoegd aan de voorkant van de prioriteitswachtrij, die wordt gevormd met behulp van gekoppelde lijsten. De functies zoals duw() , knal() , En kijkje() worden gebruikt om een prioriteitswachtrij te implementeren met behulp van een gekoppelde lijst en worden als volgt uitgelegd:
- push(): Deze functie wordt gebruikt om nieuwe gegevens in de wachtrij in te voegen. pop(): Deze functie verwijdert het element met de hoogste prioriteit uit de wachtrij. peek() / top(): Deze functie wordt gebruikt om het element met de hoogste prioriteit in de wachtrij te krijgen zonder het uit de wachtrij te verwijderen.
| Gekoppelde lijst | duw() | knal() | kijkje() |
|---|---|---|---|
| Tijdcomplexiteit | Op) | O(1) | O(1) |
C++
// C++ code to implement Priority Queue> // using Linked List> #include> using> namespace> std;> // Node> typedef> struct> node {> >int> data;> >// Lower values indicate> >// higher priority> >int> priority;> >struct> node* next;> } Node;> // Function to create a new node> Node* newNode(>int> d,>int> p)> {> >Node* temp = (Node*)>malloc>(>sizeof>(Node));> >temp->gegevens = d;> >temp->prioriteit = p;> >temp->volgende = NULL;> >return> temp;> }> // Return the value at head> int> peek(Node** head) {>return> (*head)->gegevens; }> // Removes the element with the> // highest priority form the list> void> pop(Node** head)> {> >Node* temp = *head;> >(*head) = (*head)->volgende;> >free>(temp);> }> // Function to push according to priority> void> push(Node** head,>int> d,>int> p)> {> >Node* start = (*head);> >// Create new Node> >Node* temp = newNode(d, p);> >// Special Case: The head of list has> >// lesser priority than new node> >if> ((*head)->prioriteit // Nieuw knooppunt invoegen vóór hoofd temp->next = *head; (*hoofd) = temperatuur; } else { // Doorloop de lijst en zoek een // positie om een nieuw knooppunt in te voegen while (start->volgende != NULL && start->volgende->prioriteit> p) { start = start->volgende; } // Ofwel aan het einde van de lijst // ofwel op de gewenste positie temp->next = start->next; start->volgende = temperatuur; } } // Te controleren functie is dat de lijst leeg is int isEmpty(Node** head) { return (*head) == NULL; } // Stuurprogrammacode int main() {// Maak een prioriteitswachtrij // 7->4->5->6 Node* pq = newNode(4, 1); duwen(&pq, 5, 2); duwen(&pq, 6, 3); duwen(&pq, 7, 0); while (!isEmpty(&pq)) {cout<< ' ' << peek(&pq); pop(&pq); } return 0; }> |
>
>
Java
// Java code to implement Priority Queue> // using Linked List> import> java.util.* ;> class> Solution> {> // Node> static> class> Node {> >int> data;> > >// Lower values indicate higher priority> >int> priority;> >Node next;> > }> static> Node node =>new> Node();> > // Function to Create A New Node> static> Node newNode(>int> d,>int> p)> {> >Node temp =>new> Node();> >temp.data = d;> >temp.priority = p;> >temp.next =>null>;> > >return> temp;> }> > // Return the value at head> static> int> peek(Node head)> {> >return> (head).data;> }> > // Removes the element with the> // highest priority from the list> static> Node pop(Node head)> {> >Node temp = head;> >(head) = (head).next;> >return> head;> }> > // Function to push according to priority> static> Node push(Node head,>int> d,>int> p)> {> >Node start = (head);> > >// Create new Node> >Node temp = newNode(d, p);> > >// Special Case: The head of list has lesser> >// priority than new node. So insert new> >// node before head node and change head node.> >if> ((head).priority // Insert New Node before head temp.next = head; (head) = temp; } else { // Traverse the list and find a // position to insert new node while (start.next != null && start.next.priority>p) { start = start.volgende; } // Ofwel aan het einde van de lijst // of op de gewenste positie temp.next = start.next; start.volgende = temperatuur; } retourkop; } // Functie om te controleren is dat de lijst leeg is static int isEmpty(Node head) { return ((head) == null)?1:0; } // Stuurprogrammacode public static void main(String args[]) {// Maak een prioriteitswachtrij // 7.4.5.6 Knooppunt pq = newNode(4, 1); pq =duwen(pq, 5, 2); pq =duwen(pq, 6, 3); pq =duwen(pq, 7, 0); while (isEmpty(pq)==0) { System.out.printf('%d ', peek(pq)); pq=pop(pq); } } } // Deze code is bijgedragen door ishankhandelwals.> |
>
>
Python
# Python3 code to implement Priority Queue> # using Singly Linked List> # Class to create new node which includes> # Node Data, and Node Priority> class> PriorityQueueNode:> >def> _init_(>self>, value, pr):> >self>.data>=> value> >self>.priority>=> pr> >self>.>next> => None> # Implementation of Priority Queue> class> PriorityQueue:> >def> _init_(>self>):> >self>.front>=> None> ># Method to check Priority Queue is Empty> ># or not if Empty then it will return True> ># Otherwise False> >def> isEmpty(>self>):> >return> True> if> self>.front>=>=> None> else> False> ># Method to add items in Priority Queue> ># According to their priority value> >def> push(>self>, value, priority):> ># Condition check for checking Priority> ># Queue is empty or not> >if> self>.isEmpty()>=>=> True>:> ># Creating a new node and assigning> ># it to class variable> >self>.front>=> PriorityQueueNode(value,> >priority)> ># Returning 1 for successful execution> >return> 1> >else>:> ># Special condition check to see that> ># first node priority value> >if> self>.front.priority # Creating a new node newNode = PriorityQueueNode(value, priority) # Updating the new node next value newNode.next = self.front # Assigning it to self.front self.front = newNode # Returning 1 for successful execution return 1 else: # Traversing through Queue until it # finds the next smaller priority node temp = self.front while temp.next: # If same priority node found then current # node will come after previous node if priority>= temp.next.priority: break temp = temp.next newNode = PriorityQueueNode(waarde, prioriteit) newNode.next = temp.next temp.next = newNode # Retourneert 1 voor succesvolle uitvoering return 1 # Methode om item # met hoge prioriteit te verwijderen uit the Priority Queue def pop(self): # Conditiecontrole voor controle # Priority Queue is leeg of niet als self.isEmpty() == True: return else: # Knooppunt met hoge prioriteit verwijderen uit # Priority Queue, en front # updaten met next node self.front = self.front.next return 1 # Methode om hoge prioriteit node # waarde te retourneren Niet verwijderen def peek(self): # Conditiecontrole voor het controleren van Prioriteit # Wachtrij is leeg of niet als self.isEmpty() == True: return else: return self.front.data # Methode om door Prioriteit te gaan # Queue def traverse(self): # Conditiecontrole voor het controleren van Prioriteit # Wachtrij is leeg of niet als self.isEmpty() == True: return ' Wachtrij is leeg!' else: temp = self.front while temp: print(temp.data, end=' ') temp = temp.next # Stuurprogrammacode if _name_ == '_main_': # Een exemplaar van Priority # Queue, en waarden toevoegen # 7 -> 4 -> 5 -> 6 pq = PriorityQueue() pq.push(4, 1) pq.push(5, 2) pq.push(6, 3) pq .push(7, 0) # Door prioriteitswachtrij pq.traverse() # Verwijderen van item met de hoogste prioriteit # voor prioriteitswachtrij pq.pop()> |
>
>
C#
// C# code to implement Priority Queue> // using Linked List> using> System;> class> GFG> {> >// Node> >public> class> Node> >{> >public> int> data;> >// Lower values indicate> >// higher priority> >public> int> priority;> >public> Node next;> >}> >public> static> Node node =>new> Node();> >// Function to Create A New Node> >public> static> Node newNode(>int> d,>int> p)> >{> >Node temp =>new> Node();> >temp.data = d;> >temp.priority = p;> >temp.next =>null>;> >return> temp;> >}> >// Return the value at head> >public> static> int> peek(Node head)> >{> >return> (head).data;> >}> >// Removes the element with the> >// highest priority from the list> >public> static> Node pop(Node head)> >{> >Node temp = head;> >(head) = (head).next;> >return> head;> >}> >// Function to push according to priority> >public> static> Node push(Node head,> >int> d,>int> p)> >{> >Node start = (head);> >// Create new Node> >Node temp = newNode(d, p);> >// Special Case: The head of list> >// has lesser priority than new node.> >// So insert new node before head node> >// and change head node.> >if> ((head).priority { // Insert New Node before head temp.next = head; (head) = temp; } else { // Traverse the list and find a // position to insert new node while (start.next != null && start.next.priority>p) { start = start.volgende; } // Ofwel aan het einde van de lijst // of op de gewenste positie temp.next = start.next; start.volgende = temperatuur; } retourkop; } // Functie om te controleren is dat de lijst leeg is public static int isEmpty(Node head) { return ((head) == null) ? 1: 0; } // Stuurprogrammacode public static void Main(string[] args) {// Maak een prioriteitswachtrij // 7.4.5.6 Knooppunt pq = newNode(4, 1); pq = duwen(pq, 5, 2); pq = duwen(pq, 6, 3); pq = duwen(pq, 7, 0); while (isEmpty(pq) == 0) { Console.Write('{0:D} ', peek(pq)); pq = pop(pq); } } } // Deze code is bijgedragen door ishankhandelwals.> |
>
>
Javascript
// JavaScript code to implement Priority Queue> // using Linked List> // Node> class Node {> >// Lower values indicate> >// higher priority> >constructor() {> >this>.data = 0;> >this>.priority = 0;> >this>.next =>null>;> >}> }> var> node =>new> Node();> // Function to Create A New Node> function> newNode(d, p) {> >var> temp =>new> Node();> >temp.data = d;> >temp.priority = p;> >temp.next =>null>;> >return> temp;> }> // Return the value at head> function> peek(head) {> >return> head.data;> }> // Removes the element with the> // highest priority from the list> function> pop(head) {> >var> temp = head;> >head = head.next;> >return> head;> }> // Function to push according to priority> function> push(head, d, p) {> >var> start = head;> >// Create new Node> >var> temp = newNode(d, p);> >// Special Case: The head of list> >// has lesser priority than new node.> >// So insert new node before head node> >// and change head node.> >if> (head.priority // Insert New Node before head temp.next = head; head = temp; } else { // Traverse the list and find a // position to insert new node while (start.next != null && start.next.priority>p) { start = start.volgende; } // Ofwel aan het einde van de lijst // of op de gewenste positie temp.next = start.next; start.volgende = temperatuur; } retourkop; } // Te controleren functie is dat de lijst leeg is, functie isEmpty(head) { return head == null? 1: 0; } // Stuurprogrammacode // Maak een prioriteitswachtrij // 7.4.5.6 var pq = newNode(4, 1); pq = duwen(pq, 5, 2); pq = duwen(pq, 6, 3); pq = duwen(pq, 7, 0); while (isEmpty(pq) == 0) { console.log(peek(pq),' '); pq = pop(pq); } // Deze code is bijgedragen door ishankhandelwals.> |
>
>Uitvoer
6 5 4 7>
Raadpleeg dit artikel voor meer details.
Opmerking: We kunnen ook Linked List gebruiken, de tijdcomplexiteit van alle bewerkingen met een gekoppelde lijst blijft hetzelfde als de array. Het voordeel van een gekoppelde lijst is verwijderHoogstePrioriteit() kan efficiënter zijn omdat we geen items hoeven te verplaatsen.
3) Prioriteitswachtrij implementeren met behulp van heaps:
Binaire heap heeft over het algemeen de voorkeur voor implementatie van prioriteitswachtrijen, omdat heaps betere prestaties bieden in vergelijking met arrays of LinkedList. Gezien de eigenschappen van een hoop, bevindt de ingang met de grootste sleutel zich bovenaan en kan deze onmiddellijk worden verwijderd. Het zal echter tijd O(log n) kosten om de heap-eigenschap voor de resterende sleutels te herstellen. Als echter onmiddellijk een ander item moet worden ingevoegd, kan een deel van deze tijd worden gecombineerd met de O(log n)-tijd die nodig is om het nieuwe item in te voegen. De weergave van een prioriteitswachtrij als een heap blijkt dus voordelig voor grote n, aangezien deze efficiënt wordt weergegeven in aaneengesloten opslag en gegarandeerd alleen logaritmische tijd nodig heeft voor zowel invoegingen als verwijderingen. Bewerkingen op binaire heap zijn als volgt:
- insert(p): Voegt een nieuw element in met prioriteit p. extractMax(): Extraheert een element met maximale prioriteit. remove(i): Verwijdert een element waarnaar wordt verwezen door een iterator i. getMax(): Retourneert een element met maximale prioriteit. changePriority(i, p): Verandert de prioriteit van een element waarnaar wordt verwezen ik tot p .
| Binaire hoop | invoegen() | verwijderen() | kijkje() |
|---|---|---|---|
| Tijdcomplexiteit | O(logboek n) | O(logboek n) | O(1) |
Raadpleeg dit artikel voor code-implementatie.
4) Prioriteitswachtrij implementeren met behulp van binaire zoekboom:
Een zelfbalancerende binaire zoekboom zoals AVL Tree, Red-Black Tree, etc. kan ook worden gebruikt om een prioriteitswachtrij te implementeren. Bewerkingen zoals peek(), insert() en delete() kunnen worden uitgevoerd met BST.
| Binaire zoekboom | kijkje() | invoegen() | verwijderen() |
|---|---|---|---|
| Tijdcomplexiteit | O(1) | O(logboek n) | O(logboek n) |
Toepassingen van prioriteitswachtrij:
- CPU-planning
- Grafiekalgoritmen zoals het kortste pad-algoritme van Dijkstra, Prim's Minimum Spanning Tree, enz.
- Stack-implementatie
- Alle toepassingen van Priority Queue
- Prioriteitswachtrij in C++
- Prioriteitswachtrij in Java
- Prioriteitswachtrij in Python
- Prioriteitswachtrij in JavaScript
- Recente artikelen over Prioriteitswachtrij!