A Prioritätswarteschlange ist eine Art Warteschlange, die Elemente basierend auf ihren Prioritätswerten anordnet. Elemente mit höheren Prioritätswerten werden normalerweise vor Elementen mit niedrigeren Prioritätswerten abgerufen.
In einer Prioritätswarteschlange ist jedem Element ein Prioritätswert zugeordnet. Wenn Sie der Warteschlange ein Element hinzufügen, wird es basierend auf seinem Prioritätswert an einer Position eingefügt. Wenn Sie beispielsweise ein Element mit einem hohen Prioritätswert zu einer Prioritätswarteschlange hinzufügen, wird es möglicherweise am Anfang der Warteschlange eingefügt, während ein Element mit einem niedrigen Prioritätswert möglicherweise am Ende der Warteschlange eingefügt wird.
Es gibt mehrere Möglichkeiten, eine Prioritätswarteschlange zu implementieren, einschließlich der Verwendung eines Arrays, einer verknüpften Liste, eines Heaps oder eines binären Suchbaums. Jede Methode hat ihre eigenen Vor- und Nachteile und die beste Wahl hängt von den spezifischen Anforderungen Ihrer Anwendung ab.
Prioritätswarteschlangen werden häufig in Echtzeitsystemen verwendet, bei denen die Reihenfolge, in der Elemente verarbeitet werden, erhebliche Auswirkungen haben kann. Sie werden auch in Algorithmen verwendet, um deren Effizienz zu verbessern, z Dijkstras Algorithmus zum Finden des kürzesten Pfades in einem Diagramm und der A*-Suchalgorithmus zur Pfadfindung.
Eigenschaften der Prioritätswarteschlange
Eine Prioritätswarteschlange ist also eine Erweiterung der Warteschlange mit den folgenden Eigenschaften.
- Jedem Element ist eine Priorität zugeordnet.
- Ein Element mit hoher Priorität wird vor einem Element mit niedriger Priorität aus der Warteschlange entfernt.
- Wenn zwei Elemente die gleiche Priorität haben, werden sie entsprechend ihrer Reihenfolge in der Warteschlange bedient.
In der folgenden Prioritätswarteschlange hat ein Element mit einem maximalen ASCII-Wert die höchste Priorität. Die Elemente mit höherer Priorität werden zuerst bedient.
Wie wird den Elementen in einer Prioritätswarteschlange Priorität zugewiesen?
In einer Prioritätswarteschlange wird im Allgemeinen der Wert eines Elements für die Zuweisung der Priorität berücksichtigt.
Beispielsweise wird dem Element mit dem höchsten Wert die höchste Priorität und dem Element mit dem niedrigsten Wert die niedrigste Priorität zugewiesen. Es kann auch der umgekehrte Fall verwendet werden, d. h. dem Element mit dem niedrigsten Wert kann die höchste Priorität zugewiesen werden. Außerdem kann die Priorität entsprechend unseren Bedürfnissen zugewiesen werden.
Operationen einer Prioritätswarteschlange:
Eine typische Prioritätswarteschlange unterstützt die folgenden Vorgänge:
1) Einfügung in eine Prioritätswarteschlange
Wenn ein neues Element in eine Prioritätswarteschlange eingefügt wird, wird es von oben nach unten und von links nach rechts in den leeren Steckplatz verschoben. Befindet sich das Element jedoch nicht an der richtigen Stelle, wird es mit dem übergeordneten Knoten verglichen. Wenn das Element nicht in der richtigen Reihenfolge ist, werden die Elemente vertauscht. Der Austauschvorgang wird fortgesetzt, bis alle Elemente an der richtigen Position platziert sind.
2) Löschen in einer Prioritätswarteschlange
Wie Sie wissen, ist in einem Max-Heap das maximale Element der Wurzelknoten. Dabei wird das Element mit der höchsten Priorität zuerst entfernt. Somit entfernen Sie den Root-Knoten aus der Warteschlange. Durch das Entfernen entsteht ein leerer Steckplatz, der durch neue Einfügungen weiter gefüllt wird. Anschließend wird das neu eingefügte Element mit allen Elementen in der Warteschlange verglichen, um die Heap-Invariante beizubehalten.
3) Werfen Sie einen Blick in eine Prioritätswarteschlange
Dieser Vorgang hilft dabei, das maximale Element von Max Heap oder das minimale Element von Min Heap zurückzugeben, ohne den Knoten aus der Prioritätswarteschlange zu löschen.
Arten von Prioritätswarteschlangen:
1) Prioritätswarteschlange mit aufsteigender Reihenfolge
Wie der Name schon sagt, erhält in der Prioritätswarteschlange in aufsteigender Reihenfolge das Element mit einem niedrigeren Prioritätswert eine höhere Priorität in der Prioritätsliste. Wenn wir beispielsweise die folgenden Elemente in einer Prioritätswarteschlange haben, die in aufsteigender Reihenfolge angeordnet sind, z. B. 4,6,8,9,10. Hier ist 4 die kleinste Zahl, daher erhält sie die höchste Priorität in einer Prioritätswarteschlange. Wenn wir also aus dieser Art von Prioritätswarteschlange austreten, wird 4 aus der Warteschlange entfernt und aus der Warteschlange wird 4 zurückgegeben.
2) Absteigende Prioritätswarteschlange
Wie Sie vielleicht wissen, ist der Wurzelknoten das größte Element in einem maximalen Heap. Außerdem wird zuerst das Element mit der höchsten Priorität entfernt. Dadurch wird der Root-Knoten aus der Warteschlange entfernt. Diese Löschung hinterlässt einen leeren Raum, der in Zukunft mit neuen Einfügungen gefüllt wird. Die Heap-Invariante wird dann beibehalten, indem das neu eingefügte Element mit allen anderen Einträgen in der Warteschlange verglichen wird.
Arten von Prioritätswarteschlangen
Unterschied zwischen Prioritätswarteschlange und normaler Warteschlange?
Den Elementen in einer Warteschlange wird keine Priorität zugewiesen. Die FIFO-Regel (First-In-First-Out) wird implementiert, wohingegen in einer Prioritätswarteschlange die Elemente eine Priorität haben. Die Elemente mit höherer Priorität werden zuerst bedient.
Wie implementiert man eine Prioritätswarteschlange?
Die Prioritätswarteschlange kann mithilfe der folgenden Datenstrukturen implementiert werden:
- Arrays
- Verlinkte Liste
- Heap-Datenstruktur
- Binärer Suchbaum
Lassen Sie uns all dies im Detail besprechen.
1) Implementieren Sie die Prioritätswarteschlange mithilfe eines Arrays:
Eine einfache Implementierung besteht darin, ein Array mit der folgenden Struktur zu verwenden.
Strukturelement {
int-Element;
int Priorität;
}
- enqueue(): Mit dieser Funktion werden neue Daten in die Warteschlange eingefügt. dequeue(): Diese Funktion entfernt das Element mit der höchsten Priorität aus der Warteschlange. peek()/top(): Diese Funktion wird verwendet, um das Element mit der höchsten Priorität in der Warteschlange abzurufen, ohne es aus der Warteschlange zu entfernen.
| Arrays | in die Warteschlange einreihen() | entsprechend () | spähen() |
|---|---|---|---|
| Zeitkomplexität | O(1) | An) | An) |
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
Sortieren in Arraylist in 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.> |
CSS-Grenze
>
>
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> |
>
>Ausgabe
16 14 12>
Notiz: Lesen Dieser Artikel für mehr Details.
2) Implementieren Sie die Prioritätswarteschlange mithilfe einer verknüpften Liste:
In einer LinkedList-Implementierung werden die Einträge in absteigender Reihenfolge nach ihrer Priorität sortiert. Das Element mit der höchsten Priorität wird immer am Anfang der Prioritätswarteschlange hinzugefügt, die mithilfe verknüpfter Listen gebildet wird. Die Funktionen mögen drücken() , Pop() , Und spähen() werden zur Implementierung einer Prioritätswarteschlange mithilfe einer verknüpften Liste verwendet und wie folgt erläutert:
- push(): Mit dieser Funktion werden neue Daten in die Warteschlange eingefügt. pop(): Diese Funktion entfernt das Element mit der höchsten Priorität aus der Warteschlange. peek() / top(): Diese Funktion wird verwendet, um das Element mit der höchsten Priorität in der Warteschlange abzurufen, ohne es aus der Warteschlange zu entfernen.
| Verlinkte Liste | drücken() | Pop() | spähen() |
|---|---|---|---|
| Zeitkomplexität | An) | 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->data = d;> >temp->Priorität = p;> >temp->next = NULL;> >return> temp;> }> // Return the value at head> int> peek(Node** head) {>return> (*head)->Daten; }> // Removes the element with the> // highest priority form the list> void> pop(Node** head)> {> >Node* temp = *head;> >(*head) = (*head)->weiter;> >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)->Priorität // Neuen Knoten vor Kopf einfügen temp->next = *head; (*Kopf) = temp; } else { // Durchlaufe die Liste und finde // eine Position zum Einfügen eines neuen Knotens while (start->next != NULL && start->next->priority> p) { start = start->next; } // Entweder am Ende der Liste // oder an der gewünschten Position temp->next = start->next; start->next = temp; } } // Funktion zur Überprüfung, ob die Liste leer ist int isEmpty(Node** head) { return (*head) == NULL; } // Treibercode int main() { // Eine Prioritätswarteschlange erstellen // 7->4->5->6 Node* pq = newNode(4, 1); push(&pq, 5, 2); push(&pq, 6, 3); push(&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.next; } // Entweder am Ende der Liste // oder an der gewünschten Position temp.next = start.next; start.next = temp; } return head; } // Funktion zur Überprüfung, ob die Liste leer ist static int isEmpty(Node head) { return ((head) == null)?1:0; } // Treibercode public static void main(String args[]) { // Eine Prioritätswarteschlange erstellen // 7.4.5.6 Node pq = newNode(4, 1); pq =push(pq, 5, 2); pq =push(pq, 6, 3); pq =push(pq, 7, 0); while (isEmpty(pq)==0) { System.out.printf('%d ', peek(pq)); pq=pop(pq); } } } // Dieser Code wurde von ishankhandelwals beigesteuert.> |
>
>
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(Wert, Priorität) newNode.next = temp.next temp.next = newNode # Rückgabe von 1 für erfolgreiche Ausführung return 1 # Methode zum Entfernen von Elementen mit hoher Priorität # aus the Priority Queue def pop(self): # Bedingungsprüfung zur Prüfung # Priority Queue ist leer oder nicht, wenn self.isEmpty() == True: return else: # Knoten mit hoher Priorität aus # Priority Queue entfernen und Front # mit next aktualisieren node self.front = self.front.next return 1 # Methode zur Rückgabe eines Knotens mit hoher Priorität # Wert Wird nicht entfernt def peek(self): # Bedingungsprüfung zur Überprüfung der Priorität # Warteschlange ist leer oder nicht, wenn self.isEmpty() == True: return else: return self.front.data # Methode zum Durchlaufen der Priorität # Queue def traverse(self): # Bedingungsprüfung zur Überprüfung der Priorität # Queue ist leer oder nicht, wenn self.isEmpty() == True: return ' Warteschlange ist leer!' else: temp = self.front while temp: print(temp.data, end=' ') temp = temp.next # Treibercode if _name_ == '_main_': # Erstellen einer Instanz von Priority # Queue und Hinzufügen von Werten # 7 -> 4 -> 5 -> 6 pq = PriorityQueue() pq.push(4, 1) pq.push(5, 2) pq.push(6, 3) pq .push(7, 0) # Durchlaufen der Prioritätswarteschlange pq.traverse() # Entfernen des Elements mit der höchsten Priorität # für die Prioritätswarteschlange 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.next; } // Entweder am Ende der Liste // oder an der gewünschten Position temp.next = start.next; start.next = temp; } return head; } // Funktion zur Überprüfung, ob die Liste leer ist public static int isEmpty(Node head) { return ((head) == null) ? 1 : 0; } // Treibercode public static void Main(string[] args) { // Eine Prioritätswarteschlange erstellen // 7.4.5.6 Node pq = newNode(4, 1); pq = push(pq, 5, 2); pq = push(pq, 6, 3); pq = push(pq, 7, 0); while (isEmpty(pq) == 0) { Console.Write('{0:D} ', peek(pq)); pq = pop(pq); } } } // Dieser Code wurde von ishankhandelwals beigesteuert.> |
>
>
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.next; } // Entweder am Ende der Liste // oder an der gewünschten Position temp.next = start.next; start.next = temp; } return head; } // Zu prüfende Funktion, ob die Liste leer ist function isEmpty(head) { return head == null ? 1 : 0; } // Treibercode // Eine Prioritätswarteschlange erstellen // 7.4.5.6 var pq = newNode(4, 1); pq = push(pq, 5, 2); pq = push(pq, 6, 3); pq = push(pq, 7, 0); while (isEmpty(pq) == 0) { console.log(peek(pq),' '); pq = pop(pq); } // Dieser Code wurde von ishankhandelwals beigesteuert.> |
>
>Ausgabe
6 5 4 7>
Weitere Einzelheiten finden Sie in diesem Artikel.
Notiz: Wir können auch eine verknüpfte Liste verwenden. Die zeitliche Komplexität aller Operationen mit einer verknüpften Liste bleibt dieselbe wie bei einem Array. Der Vorteil einer verknüpften Liste ist deleteHighestPriority() kann effizienter sein, da wir keine Gegenstände bewegen müssen.
Zufallszahlengenerator in c
3) Implementieren Sie die Prioritätswarteschlange mithilfe von Heaps:
Binärer Heap wird im Allgemeinen für die Implementierung von Prioritätswarteschlangen bevorzugt, da Heaps im Vergleich zu Arrays oder LinkedList eine bessere Leistung bieten. Unter Berücksichtigung der Eigenschaften eines Heaps befindet sich der Eintrag mit dem größten Schlüssel oben und kann sofort entfernt werden. Es wird jedoch Zeit O(log n) benötigen, um die Heap-Eigenschaft für die verbleibenden Schlüssel wiederherzustellen. Wenn jedoch sofort ein weiterer Eintrag eingefügt werden soll, kann ein Teil dieser Zeit mit der O(log n)-Zeit kombiniert werden, die zum Einfügen des neuen Eintrags benötigt wird. Daher erweist sich die Darstellung einer Prioritätswarteschlange als Heap für große n als vorteilhaft, da sie im zusammenhängenden Speicher effizient dargestellt wird und garantiert nur logarithmische Zeit sowohl für Einfügungen als auch für Löschungen benötigt. Die Operationen auf dem binären Heap lauten wie folgt:
- insert(p): Fügt ein neues Element mit der Priorität p ein. extractMax(): Extrahiert ein Element mit maximaler Priorität. Remove(i): Entfernt ein Element, auf das ein Iterator i zeigt. getMax(): Gibt ein Element mit maximaler Priorität zurück. changePriority(i, p): Ändert die Priorität eines Elements, auf das verwiesen wird ich zu p .
| Binärer Heap | einfügen() | entfernen() | spähen() |
|---|---|---|---|
| Zeitkomplexität | O(log n) | O(log n) | O(1) |
Informationen zur Codeimplementierung finden Sie in diesem Artikel.
4) Implementieren Sie die Prioritätswarteschlange mithilfe des binären Suchbaums:
Ein selbstausgleichender binärer Suchbaum wie AVL-Baum, Rot-Schwarz-Baum usw. kann auch zur Implementierung einer Prioritätswarteschlange verwendet werden. Operationen wie peek(), insert() und delete() können mit BST ausgeführt werden.
| Binärer Suchbaum | spähen() | einfügen() | löschen() |
|---|---|---|---|
| Zeitkomplexität | O(1) | O(log n) | O(log n) |
Anwendungen der Priority Queue:
- CPU-Planung
- Graphalgorithmen wie Dijkstras Kürzester-Pfad-Algorithmus, Prims Minimum Spanning Tree usw.
- Stack-Implementierung
- Alle Anwendungen der Prioritätswarteschlange
- Prioritätswarteschlange in C++
- Prioritätswarteschlange in Java
- Prioritätswarteschlange in Python
- Prioritätswarteschlange in JavaScript
- Aktuelle Artikel zu Priority Queue!