TechCodeview

Eine Prioritätswarteschlange ist ein abstrakter Datentyp, der sich ähnlich wie die normale Warteschlange verhält, mit der Ausnahme, dass jedes Element eine gewisse Priorität hat, d. h. das Element mit der höchsten Priorität würde in einer Prioritätswarteschlange an erster Stelle stehen. Die Priorität der Elemente in einer Prioritätswarteschlange bestimmt die Reihenfolge, in der Elemente aus der Prioritätswarteschlange entfernt werden.

Die Prioritätswarteschlange unterstützt nur vergleichbare Elemente, was bedeutet, dass die Elemente entweder in aufsteigender oder absteigender Reihenfolge angeordnet sind.

Was ist Java-Hashmap?

Angenommen, wir haben einige Werte wie 1, 3, 4, 8, 14, 22 in eine Prioritätswarteschlange eingefügt, wobei die Reihenfolge der Werte vom kleinsten zum höchsten Wert erfolgt. Daher hätte die Nummer 1 die höchste Priorität, während Nummer 22 die niedrigste Priorität hätte.

Merkmale einer Prioritätswarteschlange

Eine Prioritätswarteschlange ist eine Erweiterung einer Warteschlange, die die folgenden Merkmale enthält:

• Jedem Element in einer Prioritätswarteschlange ist eine bestimmte Priorität zugeordnet.
• Ein Element mit der höheren Priorität wird vor dem Löschen der niedrigeren Priorität gelöscht.
• Wenn zwei Elemente in einer Prioritätswarteschlange die gleiche Priorität haben, werden sie nach dem FIFO-Prinzip angeordnet.

Lassen Sie uns die Prioritätswarteschlange anhand eines Beispiels verstehen.

Wir haben eine Prioritätswarteschlange, die die folgenden Werte enthält:

1, 3, 4, 8, 14, 22

Alle Werte sind in aufsteigender Reihenfolge angeordnet. Nun werden wir beobachten, wie die Prioritätswarteschlange nach der Ausführung der folgenden Vorgänge aussehen wird:

Umfrage():Diese Funktion entfernt das Element mit der höchsten Priorität aus der Prioritätswarteschlange. In der obigen Prioritätswarteschlange hat das Element „1“ die höchste Priorität und wird daher aus der Prioritätswarteschlange entfernt.add(2):Diese Funktion fügt das Element „2“ in eine Prioritätswarteschlange ein. Da 2 das kleinste Element unter allen Zahlen ist, erhält es die höchste Priorität.Umfrage():Das Element „2“ wird aus der Prioritätswarteschlange entfernt, da es die Warteschlange mit der höchsten Priorität hat.add(5):Es fügt 5 Elemente nach 4 ein, da 5 größer als 4 und kleiner als 8 ist, sodass es die dritthöchste Priorität in einer Prioritätswarteschlange erhält.

Arten von Prioritätswarteschlangen

Es gibt zwei Arten von Prioritätswarteschlangen:

Warteschlange mit aufsteigender Priorität:In der Prioritätswarteschlange mit aufsteigender Reihenfolge wird einer niedrigeren Prioritätsnummer eine höhere Priorität in einer Priorität zugewiesen. Zum Beispiel nehmen wir die Zahlen von 1 bis 5 in aufsteigender Reihenfolge wie 1,2,3,4,5; Daher wird die kleinste Zahl, d. h. 1, als höchste Priorität in einer Prioritätswarteschlange vergeben.
Prioritätswarteschlange in absteigender Reihenfolge:In der Prioritätswarteschlange in absteigender Reihenfolge wird eine höhere Prioritätsnummer als höhere Priorität in einer Priorität angegeben. Zum Beispiel nehmen wir die Zahlen von 1 bis 5 in absteigender Reihenfolge wie 5, 4, 3, 2, 1; Daher wird die größte Zahl, d. h. 5, als höchste Priorität in einer Prioritätswarteschlange vergeben.

Darstellung der Prioritätswarteschlange

Jetzt werden wir sehen, wie die Prioritätswarteschlange durch eine Einwegliste dargestellt wird.

Wir werden die Prioritätswarteschlange erstellen, indem wir die unten angegebene Liste verwenden DIE INFO Liste enthält die Datenelemente, PRN Die Liste enthält die Prioritätsnummern aller in der Datei verfügbaren Datenelemente DIE INFO Liste, und LINK enthält grundsätzlich die Adresse des nächsten Knotens.

Lassen Sie uns Schritt für Schritt die Prioritätswarteschlange erstellen.

Java-Sortier-Arrayliste

Im Fall einer Prioritätswarteschlange gilt die Nummer mit der niedrigeren Priorität als die Nummer mit der höheren Priorität, d. h. niedrigere Prioritätszahl = höhere Priorität.

Schritt 1: In der Liste ist die Nummer mit der niedrigeren Priorität 1, deren Datenwert 333 ist. Daher wird sie wie im folgenden Diagramm gezeigt in die Liste eingefügt:

Schritt 2: Nach dem Einfügen von 333 hat die Prioritätsnummer 2 eine höhere Priorität, und die dieser Priorität zugeordneten Datenwerte sind 222 und 111. Diese Daten werden also basierend auf dem FIFO-Prinzip eingefügt; daher werden zuerst 222 und dann 111 hinzugefügt.

Schritt 3: Nach dem Einfügen der Elemente der Priorität 2 ist die nächsthöhere Prioritätszahl 4 und die den 4 Prioritätszahlen zugeordneten Datenelemente sind 444, 555, 777. In diesem Fall würden Elemente nach dem FIFO-Prinzip eingefügt; Daher werden zuerst 444, dann 555 und dann 777 hinzugefügt.

Schritt 4: Nach dem Einfügen der Elemente mit Priorität 4 ist die nächsthöhere Prioritätsnummer 5 und der mit Priorität 5 verknüpfte Wert ist 666, sodass er am Ende der Warteschlange eingefügt wird.

Implementierung der Priority Queue

Die Prioritätswarteschlange kann auf vier Arten implementiert werden, darunter Arrays, verknüpfte Listen, Heap-Datenstrukturen und binäre Suchbäume. Die Heap-Datenstruktur ist die effizienteste Methode zur Implementierung der Prioritätswarteschlange. Daher werden wir in diesem Thema die Prioritätswarteschlange mithilfe einer Heap-Datenstruktur implementieren. Nun verstehen wir zunächst den Grund, warum Heap unter allen anderen Datenstrukturen die effizienteste Methode ist.

Analyse von Komplexitäten anhand verschiedener Implementierungen

Was ist Heap?

Ein Heap ist eine baumbasierte Datenstruktur, die einen vollständigen Binärbaum bildet und die Heap-Eigenschaft erfüllt. Wenn A ein übergeordneter Knoten von B ist, wird A in Bezug auf den Knoten B für alle Knoten A und B in einem Heap geordnet. Dies bedeutet, dass der Wert des übergeordneten Knotens größer oder gleich dem Wert des untergeordneten Knotens sein kann oder dass der Wert des übergeordneten Knotens kleiner oder gleich dem Wert des untergeordneten Knotens sein kann. Daher können wir sagen, dass es zwei Arten von Heaps gibt:

Maximaler Haufen:Der maximale Heap ist ein Heap, bei dem der Wert des übergeordneten Knotens größer ist als der Wert der untergeordneten Knoten.
Min. Heap:Der Min-Heap ist ein Heap, bei dem der Wert des übergeordneten Knotens kleiner ist als der Wert der untergeordneten Knoten.

Bei beiden Heaps handelt es sich um binäre Heaps, da jeder genau zwei untergeordnete Knoten hat.

Vorrangige Warteschlangenoperationen

Die üblichen Vorgänge, die wir für eine Prioritätswarteschlange ausführen können, sind Einfügen, Löschen und Einsehen. Sehen wir uns an, wie wir die Heap-Datenstruktur beibehalten können.

Einfügen des Elements in eine Prioritätswarteschlange (maximaler Heap)

Wenn wir ein Element in eine Prioritätswarteschlange einfügen, wird es von oben nach unten und von links nach rechts in den leeren Steckplatz verschoben.

Zeichenfolge von int

Befindet sich das Element nicht an der richtigen Stelle, wird es mit dem übergeordneten Knoten verglichen. Wenn festgestellt wird, dass es nicht in der richtigen Reihenfolge ist, werden die Elemente ausgetauscht. Dieser Vorgang wird fortgesetzt, bis das Element an der richtigen Position platziert ist.

Entfernen des minimalen Elements aus der Prioritätswarteschlange

Wie wir wissen, ist in einem Max-Heap das maximale Element der Wurzelknoten. Wenn wir den Wurzelknoten entfernen, entsteht ein leerer Slot. Das zuletzt eingefügte Element wird in diesen leeren Slot eingefügt. Dann wird dieses Element mit den untergeordneten Knoten, d. h. dem linken und rechten untergeordneten Knoten, verglichen und mit dem kleineren der beiden ausgetauscht. Es bewegt sich so lange im Baum nach unten, bis die Heap-Eigenschaft wiederhergestellt ist.

Anwendungen der Prioritätswarteschlange

Im Folgenden sind die Anwendungen der Prioritätswarteschlange aufgeführt:

• Es wird im Dijkstra-Algorithmus für den kürzesten Weg verwendet.
• Es wird im Prim-Algorithmus verwendet
• Es wird in Datenkomprimierungstechniken wie dem Huffman-Code verwendet.
• Es wird bei der Heap-Sortierung verwendet.
• Es wird auch in Betriebssystemen wie Prioritätsplanung, Lastausgleich und Interrupt-Verarbeitung verwendet.

Programm zum Erstellen der Prioritätswarteschlange mithilfe des binären Max-Heaps.

 #include #include int heap[40]; int size=-1; // retrieving the parent node of the child node int parent(int i) { return (i - 1) / 2; } // retrieving the left child of the parent node. int left_child(int i) { return i+1; } // retrieving the right child of the parent int right_child(int i) { return i+2; } // Returning the element having the highest priority int get_Max() { return heap[0]; } //Returning the element having the minimum priority int get_Min() { return heap[size]; } // function to move the node up the tree in order to restore the heap property. void moveUp(int i) { while (i &gt; 0) { // swapping parent node with a child node if(heap[parent(i)] <heap[i]) 2 { int temp; temp="heap[parent(i)];" heap[parent(i)]="heap[i];" heap[i]="temp;" } updating the value of i to function move node down tree in order restore heap property. void movedown(int k) index="k;" getting location left child if (left heap[index]) right (right k is not equal (k !="index)" heap[index]="heap[k];" heap[k]="temp;" movedown(index); removing element maximum priority removemax() r="heap[0];" heap[0]="heap[size];" size="size-1;" movedown(0); inserting a queue insert(int p) + 1; heap[size]="p;" up maintain property moveup(size); from at given i. delete(int i) stored ith shifted root moveup(i); having removemax(); main() elements insert(20); insert(19); insert(21); insert(18); insert(12); insert(17); insert(15); insert(16); insert(14); printf('elements are : '); for(int printf('%d ',heap[i]); delete(2); deleting whose 2. printf('
elements after max="get_Max();" printf('
the which highest %d: ',max); min="get_Min();" minimum %d',min); return 0; < pre> <p> <strong>In the above program, we have created the following functions:</strong> </p> <ul> <tr><td>int parent(int i):</td> This function returns the index of the parent node of a child node, i.e., i. </tr><tr><td>int left_child(int i):</td> This function returns the index of the left child of a given index, i.e., i. </tr><tr><td>int right_child(int i):</td> This function returns the index of the right child of a given index, i.e., i. </tr><tr><td>void moveUp(int i):</td> This function will keep moving the node up the tree until the heap property is restored. </tr><tr><td>void moveDown(int i):</td> This function will keep moving the node down the tree until the heap property is restored. </tr><tr><td>void removeMax():</td> This function removes the element which is having the highest priority. </tr><tr><td>void insert(int p):</td> It inserts the element in a priority queue which is passed as an argument in a function <strong>.</strong>  </tr><tr><td>void delete(int i):</td> It deletes the element from a priority queue at a given index. </tr><tr><td>int get_Max():</td> It returns the element which is having the highest priority, and we know that in max heap, the root node contains the element which has the largest value, and highest priority. </tr><tr><td>int get_Min():</td> It returns the element which is having the minimum priority, and we know that in max heap, the last node contains the element which has the smallest value, and lowest priority. </tr></ul> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/03/what-is-priority-queue-9.webp" alt="Priority Queue"> <hr></heap[i])>