Menü

Datenstruktur der Prioritätswarteschlange in C ++ mit Abbildung

  • Haupt
  • Andere
  • Datenstruktur der Prioritätswarteschlange in C ++ mit Abbildung

priority queue data structure c with illustration

Versuchen Sie Unser Instrument, Um Probleme Zu Beseitigen

Einführung in die Prioritätswarteschlange in C ++ mit Illustration.

Die Prioritätswarteschlange ist eine Erweiterung der Warteschlange, die wir in unserem letzten Lernprogramm besprochen haben.

Es ähnelt in bestimmten Aspekten der Warteschlange und unterscheidet sich dennoch in folgenden Punkten von der normalen Warteschlange:

  • Jedes Element in der Prioritätswarteschlange ist einer Priorität zugeordnet.
  • Das Element mit der höchsten Priorität ist das erste Element, das aus der Warteschlange entfernt wird.
  • Wenn mehr als ein Element dieselbe Priorität hat, wird deren Reihenfolge in der Warteschlange berücksichtigt.

=> Klicken Sie hier für die Absolute C ++ - Schulungsserie.

Prioritätswarteschlange in C ++

Wir können die Prioritätswarteschlange als modifizierte Version der Warteschlange visualisieren, mit der Ausnahme, dass das Element mit der höchsten Priorität zuerst abgerufen wird, wenn das Element aus der Warteschlange entfernt werden soll. Daher bevorzugen wir die Verwendung der Prioritätswarteschlangen anstelle der Warteschlangen, wenn wir die Elemente basierend auf der Priorität verarbeiten müssen.

Was du lernen wirst:

Grundoperationen

Lassen Sie uns einige der grundlegenden Operationen diskutieren, die von der Prioritätswarteschlange unterstützt werden.

  • Einfügen (Element, Priorität): Fügt ein Element mit einer bestimmten Priorität in die Prioritätswarteschlange ein.
  • getHighestPriority (): Gibt einen Artikel mit der höchsten Priorität zurück.
  • deleteHighestPriority (): Entfernt ein Element mit der höchsten Priorität.

Abgesehen von den oben genannten Operationen können wir auch die normalen Warteschlangenoperationen wie isEmpty (), isFull () und peek () verwenden.

Illustration

Lassen Sie uns eine Illustration der Prioritätswarteschlange sehen. Der Einfachheit halber werden ASCII-Zeichen als Elemente in der Prioritätswarteschlange verwendet. Je höher der ASCII-Wert ist, desto höher ist die Priorität.

Ausgangszustand - Priority Queue (PQ) - {} => leer

Abbildung der Prioritätswarteschlange

Aus der obigen Abbildung geht hervor, dass die Einfügeoperation einer normalen Warteschlange ähnelt. Wenn wir jedoch 'deleteHighestPriority' für die Prioritätswarteschlange aufrufen, wird zuerst das Element mit der höchsten Priorität entfernt.

Wenn wir diese Funktion zum ersten Mal aufrufen, wird Element O entfernt, während beim zweiten Mal das Element M entfernt wird, da es eine höhere Priorität als G und A hat.

Implementierung von Prioritätswarteschlangen in C ++

Prioritätswarteschlangen können implementiert werden mit:

# 1) Arrays / verknüpfte Listen

Wir können die Prioritätswarteschlangen mithilfe von Arrays implementieren. Dies ist die einfachste Implementierung für die Prioritätswarteschlangen.

Um die Elemente in der Prioritätswarteschlange darzustellen, können wir eine Struktur wie folgt deklarieren:

struct pq_item{ int item; int priority; };

Wir haben auch die Priorität für jeden Artikel angegeben.

Um ein neues Element in die Prioritätswarteschlange einzufügen, müssen Sie das Element einfach am Ende des Arrays einfügen.

Um das Element mit getHighestPriority () aus der Warteschlange zu holen, müssen wir das Array von Anfang an durchlaufen und das Element mit der höchsten Priorität zurückgeben.

Um das Element mithilfe der Operation deleteHighestPriority aus der Warteschlange zu entfernen, müssen Sie das gesamte Array durchlaufen und das Element mit der höchsten Priorität löschen. Verschieben Sie dann alle anderen Elemente nach dem gelöschten Element um eine Position zurück.

Wir können die Prioritätswarteschlange auch mithilfe einer verknüpften Liste implementieren. Wir können alle Operationen auf ähnliche Weise wie Arrays ausführen. Der einzige Unterschied besteht darin, dass wir die Elemente nach dem Aufruf von deleteHighestPriority nicht verschieben müssen.

# 2) Haufen

Die Verwendung von Heaps zum Implementieren einer Prioritätswarteschlange ist der effizienteste Weg und bietet im Vergleich zu verknüpften Listen und Arrays eine viel bessere Leistung. Im Gegensatz zur verknüpften Liste und zum verknüpften Array benötigt die Heap-Implementierung O (logn) Zeit zum Einfügen und Löschen von Vorgängen in der Prioritätswarteschlange. Get operation, getHighestPriority benötigt O (1) Zeit.

# 3) Eingebaute Prioritätswarteschlange in der Standardvorlagenbibliothek (STL) in C ++

In C ++ haben wir eine Prioritätswarteschlange als adaptive Containerklasse, die so konzipiert ist, dass das höchste Element das erste Element in der Warteschlange ist und alle Elemente in absteigender Reihenfolge vorliegen.

Somit hat jedes Element in der Prioritätswarteschlange eine feste Priorität.

Wir haben eine Klasse in STL, die die Implementierung der Prioritätswarteschlange enthält.

Die verschiedenen von der Prioritätswarteschlange unterstützten Vorgänge lauten wie folgt:

  1. priority_queue :: size (): Gibt die Größe der Warteschlange zurück.
  2. priority_queue :: empty (): Überprüft, ob die Warteschlange leer ist und gibt ihren Status zurück.
  3. priority_queue :: top (): Gibt einen Verweis auf das oberste Element der Prioritätswarteschlange zurück.
  4. priority_queue :: push (): Fügt ein Element am Ende der Prioritätswarteschlange hinzu.
  5. priority_queue :: pop (): Entfernt das erste Element aus der Prioritätswarteschlange.
  6. priority_queue :: swap (): Wird verwendet, um den Inhalt einer Prioritätswarteschlange gegen eine andere des gleichen Typs und der gleichen Größe auszutauschen.
  7. Werttyp der Prioritätswarteschlange: Der Werttyp gibt den Typ des Elements an, das in einer Prioritätswarteschlange gespeichert ist. Dies dient auch als Synonym für den Vorlagenparameter.
  8. priority_queue :: emplace (): Wird verwendet, um ein neues Element in den Prioritätswarteschlangencontainer oben in der Warteschlange einzufügen.

Im nächsten Programm sehen wir die Funktionalität der Prioritätswarteschlange in STL in 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; }

Ausgabe:

sql plsql Interview Fragen und Antworten

Größe der Warteschlange (pq.size ()): 5
Oberstes Element der Warteschlange (pq.top ()): 9
Die Prioritätswarteschlange pq lautet: 9 7 5 3 1
Prioritätswarteschlange nach der Operation pq.pop (): 7 5 3 1

Java-Implementierung für Priority Queue

Die Prioritätswarteschlange in Java ist eine spezielle Warteschlange, in der alle Elemente in der Warteschlange nach natürlicher Reihenfolge oder benutzerdefinierter Reihenfolge unter Verwendung eines mit der Warteschlange gelieferten Komparators sortiert werden.

Eine Prioritätswarteschlange in Java sieht wie folgt aus:

Java-Implementierung für Prioritätswarteschlange

In der Java-Prioritätswarteschlange sind die Elemente so angeordnet, dass sich das kleinste Element vorne in der Warteschlange und das größte Element hinten in der Warteschlange befindet. Wenn wir also das Element aus der Prioritätswarteschlange entfernen, wird immer das kleinste Element entfernt.

Die Klasse, die die Prioritätswarteschlange in Java implementiert, ist 'PriorityQueue' und Teil des Sammlungsframeworks von Java. Es implementiert die 'Queue' -Schnittstelle von Java.

Im Folgenden finden Sie die Klassenhierarchie für die Java PriorityQueue-Klasse.

Klassenhierarchie für die Java PriorityQueue-Klasse

Im Folgenden finden Sie ein Beispiel für die Funktionalität der Prioritätswarteschlange mit Ganzzahlen als Elemente in 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

Ausgabe:

peek () :: Kopfwert: 1
Die Prioritätswarteschlange:
1 3 5 7
Nach der Funktion poll () Prioritätswarteschlange:
3 7 5
Nach der Funktion Entfernen (5) Prioritätswarteschlange:
3 7
Die Prioritätswarteschlange enthält 3?: True
Array-Elemente:
Wert: 3
Wert: 7

Im obigen Programm verwenden wir die PriorityQueue-Klasse von Java, um ein Objekt von PriorityQueue zu erstellen, das ein Integer-Objekt enthält. Wir fügen der Warteschlange Elemente mit der Funktion 'Hinzufügen' hinzu. Dann wird die Funktion poll () aufgerufen und das Element an der Vorderseite der Warteschlange gelöscht, das zufällig das kleinste Element ist.

Wieder rufen wir die Funktion 'remove ()' auf, mit der das als Parameter angegebene Element aus der Warteschlange entfernt wird. Wir verwenden auch die Funktion 'Contains ()', um zu überprüfen, ob ein bestimmtes Element in der Warteschlange vorhanden ist. Schließlich konvertieren wir die Warteschlange mit der Funktion „toArray ()“ in ein Array-Objekt.

Anwendung

  • Betriebssystem Load Balancing und Interrupt-Handler: Betriebssystemfunktionen wie Lastausgleich und Interrupt-Behandlung werden mithilfe von Prioritätswarteschlangen implementiert. Die Lastausgleichsaktivität plant die Ressourcen mit der höchsten Priorität, um unseren Lastausgleich effektiv durchzuführen. Die Interrupt-Behandlung erfolgt durch Wartung der Interrupts mit der höchsten Priorität. Diese Funktionalität kann mithilfe der Prioritätswarteschlangen effektiv implementiert werden.
  • Routing: Routing ist eine Funktion, mit der die Netzwerkressourcen so geroutet werden, dass ein maximaler Durchsatz bei minimaler Bearbeitungszeit erzielt wird. Dies kann auch über die Prioritätswarteschlange implementiert werden.
  • Krankenhausnotfall: In einer Notaufnahme eines Krankenhauses werden die Patienten entsprechend dem Zustand des Patienten betreut. Dies kann mithilfe von Prioritätswarteschlangen simuliert werden.
  • Dijkstras Algorithmus für den kürzesten Weg: Hier wird das Diagramm als Adjazenzliste gespeichert, und wir können eine Prioritätswarteschlange verwenden, um die minimal gewichtete Kante effizient aus der Adjazenzliste zu extrahieren und den Dijkstra-Algorithmus für den kürzesten Pfad zu implementieren.
  • Die Prioritätswarteschlange kann auch zum Speichern von Knotenschlüsseln und zum Extrahieren des minimalen Schlüsselknotens verwendet werden, während der Spanning Tree implementiert wird.

Fazit

Prioritätswarteschlangen sind nichts anderes als die Erweiterung der Warteschlange. Im Gegensatz zu Warteschlangen, die Elemente mithilfe des FIFO-Ansatzes hinzufügen / entfernen, werden die Elemente in der Prioritätswarteschlange entsprechend der Priorität aus der Warteschlange entfernt. Somit ist jedem Element in der Warteschlange eine Priorität zugeordnet, und das Element mit der höchsten Priorität ist das erste, das aus der Warteschlange entfernt wird.

Die Prioritätswarteschlange hat drei Hauptoperationen, d. H. Insert (), getHighestPriority () und deleteHighestPriority (). Die Prioritätswarteschlange kann mithilfe von Arrays oder verknüpften Listen implementiert werden, die Arbeit ist jedoch nicht sehr effizient. Die Prioritätswarteschlange kann auch mithilfe von Heaps implementiert werden, und die Leistung ist viel schneller.

In C ++ haben wir auch eine Containerklasse, die die Funktionalität einer Prioritätswarteschlange implementiert. In Java gibt es eine integrierte Klasse priority_queue, die die Funktionalität einer Prioritätswarteschlange bereitstellt.

Die Prioritätswarteschlange wird hauptsächlich in Anwendungen verwendet, bei denen Elemente entsprechend der Priorität verarbeitet werden müssen. Zum Beispiel, Es wird bei der Interrupt-Behandlung verwendet.

In unserem nächsten Tutorial erfahren Sie alles über die kreisförmige Warteschlange, die eine weitere Erweiterung der Warteschlange darstellt.

=> Besuchen Sie hier für den vollständigen C ++ - Kurs von Experten.

Literatur-Empfehlungen

^