Prioritätswarteschlange in der Datenstruktur: Eigenschaften, Typen und Implementierung

Veröffentlicht: 2021-05-02

Inhaltsverzeichnis

Einführung

Die Priority-Queue in der Datenstruktur ist eine Erweiterung der „normalen“ Queue. Es ist ein abstrakter Datentyp, der eine Gruppe von Elementen enthält. Es ist wie die „normale“ Warteschlange, außer dass die Entnahmeelemente einer Prioritätsreihenfolge folgen. Die Prioritätsreihenfolge entfernt zuerst die Elemente mit der höchsten Priorität. Dieser Blog vermittelt Ihnen ein tieferes Verständnis der Prioritätswarteschlange und ihrer Implementierung in der Programmiersprache C.

Was ist eine Prioritätswarteschlange?

Es ist ein abstrakter Datentyp, der eine Möglichkeit bietet, das Dataset zu verwalten. Die „normale“ Warteschlange folgt einem First-in-First-out-Muster. Es holt Elemente in derselben Reihenfolge aus der Warteschlange, die zum Zeitpunkt des Einfügevorgangs verfolgt wurde. Die Elementreihenfolge in einer Prioritätswarteschlange hängt jedoch von der Priorität des Elements in dieser Warteschlange ab. Die Prioritätswarteschlange verschiebt die Elemente mit der höchsten Priorität an den Anfang der Prioritätswarteschlange und die Elemente mit der niedrigsten Priorität an das Ende der Prioritätswarteschlange.

Es unterstützt nur die Elemente, die vergleichbar sind. Daher ordnet eine Prioritätswarteschlange in der Datenstruktur die Elemente entweder in aufsteigender oder absteigender Reihenfolge an.

Sie können sich eine Prioritätswarteschlange als mehrere Patienten vorstellen, die in einem Krankenhaus anstehen. Dabei bestimmt die Situation des Patienten die Prioritätenfolge. Der Patient mit der schwersten Verletzung wäre der erste in der Warteschlange.

Was sind die Merkmale einer Prioritätswarteschlange?

Eine Warteschlange wird als Prioritätswarteschlange bezeichnet, wenn sie die folgenden Eigenschaften aufweist:

  • Jedem Element ist eine bestimmte Priorität zugeordnet.
  • Ein Element mit der höchsten Priorität wird nach vorne verschoben und zuerst gelöscht.
  • Wenn zwei Elemente denselben Prioritätswert teilen, folgt die Prioritätswarteschlange dem First-in-First-out-Prinzip für den Betrieb der Warteschlange.

Welche Arten von Prioritätswarteschlangen gibt es?

Es gibt zwei Arten von Prioritätswarteschlangen:

  • Prioritätswarteschlange in aufsteigender Reihenfolge
  • Prioritätswarteschlange in absteigender Reihenfolge

Prioritätswarteschlange in aufsteigender Reihenfolge

Eine Prioritätswarteschlange mit aufsteigender Reihenfolge gibt der niedrigeren Nummer in dieser Warteschlange die höchste Priorität. Zum Beispiel haben Sie sechs Zahlen in der Prioritätswarteschlange, die 4, 8, 12, 45, 35, 20 sind. Zuerst werden Sie diese Zahlen in aufsteigender Reihenfolge anordnen. Die neue Liste sieht wie folgt aus: 4, 8, 12, 20, 35, 45. In dieser Liste ist 4 die kleinste Zahl. Daher behandelt die Prioritätswarteschlange in aufsteigender Reihenfolge Nummer 4 als höchste Priorität.

4 8 12 20 35 45

In der obigen Tabelle hat 4 die höchste Priorität und 45 die niedrigste Priorität.

Prioritätswarteschlange in absteigender Reihenfolge

Eine Prioritätswarteschlange in absteigender Reihenfolge gibt der höchsten Nummer in dieser Warteschlange die höchste Priorität. Zum Beispiel haben Sie sechs Zahlen in der Prioritätswarteschlange, die 4, 8, 12, 45, 35, 20 sind. Zuerst werden Sie diese Zahlen in aufsteigender Reihenfolge anordnen. Die neue Liste lautet wie folgt: 45, 35, 20, 12, 8, 4. In dieser Liste ist 45 die höchste Zahl. Daher behandelt die Prioritätswarteschlange in absteigender Reihenfolge die Nummer 45 als höchste Priorität.

45 35 20 12 8 4

In der obigen Tabelle hat 4 die niedrigste Priorität und 45 die höchste Priorität.

Implementierung der Prioritätswarteschlange in der Datenstruktur

Sie können die Prioritätswarteschlangen auf eine der folgenden Arten implementieren:

  • Verlinkte Liste
  • Binärer Haufen
  • Arrays
  • Binärer Suchbaum

Der binäre Heap ist die effizienteste Methode zur Implementierung der Prioritätswarteschlange in der Datenstruktur .

Die folgenden Tabellen fassen die Komplexität verschiedener Operationen in einer Prioritätswarteschlange zusammen.

Operation Ungeordnetes Array Geordnetes Feld Binärer Heap Binärer Suchbaum
Einfügung 0(1) 0 (N) 0(log(N)) 0(log(N))
Spähen 0 (N) 0(1) 0(1) 0(1)
Löschen 0 (N) 0(1) 0(log (N)) 0(log(N))

Binärer Heap

Ein binärer Heap-Baum organisiert alle übergeordneten und untergeordneten Knoten des Baums in einer bestimmten Reihenfolge. In einem binären Heap-Baum kann ein übergeordneter Knoten maximal 2 untergeordnete Knoten haben. Der Wert des übergeordneten Knotens könnte entweder sein:

  • gleich oder kleiner als der Wert eines untergeordneten Knotens.
  • gleich oder größer als der Wert eines untergeordneten Knotens.

Der obige Prozess teilt den binären Heap in zwei Typen: Max-Heap und Min-Heap.

Max Haufen

Der Max-Heap ist ein binärer Heap, in dem ein übergeordneter Knoten einen Wert hat, der entweder gleich oder größer als der Wert des untergeordneten Knotens ist. Der Wurzelknoten des Baums hat den höchsten Wert.

Einfügen eines Elements in einen Max-Heap-Binärbaum

Sie können die folgenden Schritte ausführen, um ein Element/eine Nummer in die Prioritätswarteschlange in der Datenstruktur einzufügen .

  1. Der Algorithmus scannt den Baum von oben nach unten und von links nach rechts, um einen leeren Platz zu finden. Anschließend fügt es das Element am letzten Knoten im Baum ein.
  2. Nach dem Einfügen des Elements ist die Ordnung des Binärbaums gestört. Sie müssen die Daten untereinander austauschen, um die Reihenfolge des Max-Heap-Binärbaums zu sortieren. Sie müssen die Daten so lange mischen, bis der Baum die Max-Heap-Eigenschaft erfüllt.

Algorithmus zum Einfügen eines Elements in einen Max-Heap-Binärbaum

Wenn der Baum leer ist und keinen Knoten enthält,

Erstellen Sie einen neuen übergeordneten Knoten newElement.

sonst (ein Elternknoten ist bereits vorhanden)

Fügen Sie das neue Element am Ende des Baums ein (d. h. letzter Knoten des Baums von links nach rechts).

max-heapify den Baum

Löschen eines Elements in einem Max-Heap-Binärbaum

  1. Sie können die folgenden Schritte ausführen, um ein Element in der Prioritätswarteschlange in der Datenstruktur zu löschen .
  2. Wählen Sie das Element aus, das Sie aus dem Binärbaum löschen möchten.
  3. Verschieben Sie die Daten am Ende des Baums, indem Sie sie mit den Daten des letzten Knotens austauschen.
  4. Entfernen Sie das letzte Element des Binärbaums.
  5. Nach dem Löschen des Elements ist die Ordnung des Binärbaums gestört. Sie müssen die Reihenfolge sortieren, um die Eigenschaft von max-heap zu erfüllen. Sie müssen die Daten so lange mischen, bis der Baum die Eigenschaft max-heap erfüllt.

Algorithmus zum Löschen eines Elements in einem Max-Heap-Binärbaum

Wenn das ElementUpForDeletion der lastNode ist,

lösche das ElementUpForDeletion

Andernfalls ersetzen Sie elementUpForDeletion durch lastNode

lösche das ElementUpForDeletion

max-heapify den Baum

Finden Sie das maximale oder minimale Element in einem Max-Heap-Binärbaum

In einem binären Max-Heap-Baum gibt die Suchoperation den Elternknoten (das höchste Element) des Baums zurück.

Algorithmus zum Finden des Maximums oder Minimums in einem Max-Heap-Binärbaum

ParentNode zurückgeben

Programmimplementierung der Priority Queue unter Verwendung des Max Heap Binary Tree

#include <stdio.h>

int binär_baum = 10;

int max_heap = 0;

const int test = 100000;

void swap( int *x, int *y ) {

int ein;

a = *x;

*x= *y;

*y = ein;

}

//Code zum Finden des Elternteils im Max-Heap-Baum

int findParentNode(int node[], int root) {

if ((root > 1) && (root <binary_tree)) {

gib root/2 zurück;

}

Rückgabe -1;

}

void max_heapify(int node[], int root) {

int leftNodeRoot = findLeftChild (Knoten, Wurzel);

int rightNodeRoot = findRightChild (Knoten, Wurzel);

// am höchsten unter Wurzel, linkem Kind und rechtem Kind finden

int höchste = Wurzel;

if ((leftNodeRoot <= max_heap) && (leftNodeRoot >0)) {

if (node[leftNodeRoot] > node[highest]) {

höchste = leftNodeRoot;

}

}

if ((rightNodeRoot <= max_heap) && (rightNodeRoot >0)) {

if (node[rightNodeRoot] > node[highest]) {

höchste = rightNodeRoot;

}

}

if (höchste != Wurzel) {

swap(&node[root], &node[höchste]);

max_heapify (Knoten, am höchsten);

}

}

void create_max_heap(int node[]) {

int d;

for(d=max_haufen/2; d>=1; d–) {

max_heapify (Knoten, d);

}

}

int maximum(int node[]) {

Rückkehrknoten[1];

}

int find_max(int ​​node[]) {

int maxNode = Knoten[1];

node[1] = node[max_heap];

max_haufen–;

max_heapify (Knoten, 1);

maxNode zurückgeben;

}

void descend_key(int node[], int node, int key) {

A[root] = Schlüssel;

max_heapify (Knoten, Wurzel);

}

void enlarge_key(int node[], int root, int key) {

Knoten [Wurzel] = Schlüssel;

while((root>1) && (node[findParentNode(node, root)] < node[root])) {

swap(&node[root], &node[findParentNode(node, root)]);

root = findParentNode (Knoten, Wurzel);

}

}

void insert(int node[], int key) {

max_heap++;

node[max_heap] = -1*test;

raise_key(node, max_heap, key);

}

void display_heap(int node[]) {

int d;

for(d=1; d<=max_heap; d++) {

printf(“%d\n”,Knoten[d]);

}

printf(“\n”);

}

int Haupt() {

int node[binary_tree];

Einfügen (Knoten, 10);

Einfügen (Knoten, 4);

Einfügen (Knoten, 20);

Einfügen (Knoten, 50);

Einfügen (Knoten, 1);

Einfügen (Knoten, 15);

display_heap (Knoten);

printf(“%d\n\n”, Maximum(Knoten));

display_heap (Knoten);

printf(“%d\n”, extract_max(node));

printf(“%d\n”, extract_max(node));

0 zurückgeben;

}

Min Haufen

Der Min-Heap ist ein binärer Heap, in dem ein Elternknoten einen Wert hat, der gleich oder kleiner als der Wert des Kindknotens ist. Der Wurzelknoten des Baums hat den niedrigsten Wert.

Sie können den Min-Heap auf die gleiche Weise wie den Max-Heap implementieren, außer dass Sie die Reihenfolge umkehren.

Fazit

Die im Artikel aufgeführten Beispiele dienen nur der Erläuterung. Sie können die oben angegebenen Anweisungen gemäß Ihren Anforderungen ändern. In diesem Blog haben wir das Konzept der Prioritätswarteschlange in der Datenstruktur kennengelernt . Sie können das Beispiel ausprobieren, um Ihr Wissen über Datenstrukturen zu festigen.

Wenn Sie neugierig sind, etwas über Data Science zu lernen, schauen Sie sich das Executive PG Program in Data Science von IIIT-B & upGrad an, das für Berufstätige entwickelt wurde und mehr als 10 Fallstudien und Projekte, praktische Workshops, Mentoring mit Branchenexperten, 1 -on-1 mit Branchenmentoren, mehr als 400 Stunden Lern- und Jobunterstützung bei Top-Unternehmen.

Lernen Sie Data Science-Kurse online von den besten Universitäten der Welt. Verdienen Sie Executive PG-Programme, Advanced Certificate-Programme oder Master-Programme, um Ihre Karriere zu beschleunigen.

Was sind die Anwendungen einer Prioritätswarteschlange?

Die Prioritätswarteschlange ist eine spezielle Warteschlange, in die die Elemente auf der Grundlage ihrer Priorität eingefügt werden. Dieses Merkmal erweist sich bei der Implementierung verschiedener anderer Datenstrukturen als nützlich. Im Folgenden sind einige der beliebtesten Anwendungen der Prioritätswarteschlange aufgeführt:
 1. Dijkstras Shortest-Path-Algorithmus: Die Prioritätswarteschlange kann in Dijkstras Shortest-Path-Algorithmus verwendet werden, wenn der Graph in Form der Adjazenzliste gespeichert wird.
 2. Der Algorithmus von Prim: Der Algorithmus von Prim verwendet die Prioritätswarteschlange für die Werte oder Schlüssel von Knoten und zieht bei jedem Schritt das Minimum dieser Werte heraus.
 Datenkomprimierung : Huffman-Codes verwenden die Prioritätswarteschlange, um die Daten zu komprimieren.
 Betriebssysteme: Die Prioritätswarteschlange ist für Betriebssysteme in verschiedenen Prozessen wie Lastausgleich und Unterbrechungsbehandlung sehr nützlich.

Welcher Ansatz wird bei der Implementierung der Prioritätswarteschlange mit Array verwendet?

Der Ansatz, der bei der Implementierung der Prioritätswarteschlange unter Verwendung eines Arrays verwendet wird, ist einfach. Eine Struktur wird erstellt, um die Werte und die Priorität des Elements zu speichern, und dann wird das Array dieser Struktur erstellt, um die Elemente zu speichern. Die folgenden Operationen sind an dieser Implementierung beteiligt:
 1. enqueue() – Diese Funktion fügt die Elemente am Ende der Warteschlange ein.
 2. peek() – Diese Funktion durchläuft das Array, um das Element mit der höchsten Priorität zurückzugeben. Wenn es zwei Elemente mit derselben Priorität findet, gibt es das Element mit dem höchsten Wert unter ihnen zurück.
 3. dequeue() - Diese Funktion verschiebt alle Elemente um 1 Position nach links von dem Element, das von der Funktion peek() zurückgegeben wird, und verringert die Größe.

Was ist der Unterschied zwischen maximalem Heap und minimalem Heap?

Im Folgenden wird der Unterschied zwischen Max-Heap und Min-Heap veranschaulicht.
 Min-Heap – In einem Min-Heap muss der Schlüssel des Wurzelknotens kleiner oder gleich den Schlüsseln seiner untergeordneten Knoten sein. Es verwendet aufsteigende Priorität. Der Knoten mit dem kleinsten Schlüssel hat die Priorität. Das kleinste Element wird vor jedem anderen Element eingefügt.
 Max-Heap – In einem Max-Heap muss der Schlüssel des Wurzelknotens größer oder gleich dem Schlüssel der untergeordneten Knoten sein. Es verwendet absteigende Priorität. Der Knoten mit dem größten Schlüssel hat die Priorität. Das größte Element wird vor allen anderen Elementen eingefügt.