Datenstruktur der Prioritätswarteschlange

In diesem Tutorial erfahren Sie, welche Prioritätswarteschlange besteht. Außerdem erfahren Sie mehr über die Implementierungen in Python, Java, C und C ++.

Eine Prioritätswarteschlange ist ein spezieller Warteschlangentyp, bei dem jedes Element einer Priorität zugeordnet ist und entsprechend seiner Priorität bedient wird. Wenn Elemente mit derselben Priorität auftreten, werden sie gemäß ihrer Reihenfolge in der Warteschlange bereitgestellt.

Im Allgemeinen wird der Wert des Elements selbst für die Zuweisung der Priorität berücksichtigt.

Beispielsweise wird das Element mit dem höchsten Wert als Element mit der höchsten Priorität betrachtet. In anderen Fällen können wir jedoch das Element mit dem niedrigsten Wert als Element mit der höchsten Priorität annehmen. In anderen Fällen können wir Prioritäten entsprechend unseren Bedürfnissen setzen.

Element mit der höchsten Priorität entfernen

Unterschied zwischen Prioritätswarteschlange und normaler Warteschlange

In einer Warteschlange wird die First-In-First-Out-Regel implementiert, während in einer Prioritätswarteschlange die Werte auf der Grundlage der Priorität entfernt werden . Das Element mit der höchsten Priorität wird zuerst entfernt.

Implementierung der Prioritätswarteschlange

Die Prioritätswarteschlange kann mithilfe eines Arrays, einer verknüpften Liste, einer Heap-Datenstruktur oder eines binären Suchbaums implementiert werden. Unter diesen Datenstrukturen bietet die Heap-Datenstruktur eine effiziente Implementierung von Prioritätswarteschlangen.

Daher werden wir die Heap-Datenstruktur verwenden, um die Prioritätswarteschlange in diesem Lernprogramm zu implementieren. Ein Max-Heap wird in den folgenden Operationen implementiert. Wenn Sie mehr darüber erfahren möchten, besuchen Sie bitte max-heap und mean-heap.

Eine vergleichende Analyse verschiedener Implementierungen der Prioritätswarteschlange ist unten angegeben.

Operationen	spähen	einfügen	löschen
Verknüpfte Liste	`O(1)`	`O(n)`	`O(1)`
Binärer Haufen	`O(1)`	`O(log n)`	`O(log n)`
Binärer Suchbaum	`O(1)`	`O(log n)`	`O(log n)`

Priority Queue-Vorgänge

Grundlegende Operationen einer Prioritätswarteschlange sind das Einfügen, Entfernen und Spähen von Elementen.

Bevor Sie die Prioritätswarteschlange untersuchen, lesen Sie bitte die Heap-Datenstruktur, um ein besseres Verständnis des binären Heaps zu erhalten, der zum Implementieren der Prioritätswarteschlange in diesem Artikel verwendet wird.

1. Einfügen eines Elements in die Prioritätswarteschlange

Das Einfügen eines Elements in eine Prioritätswarteschlange (max-heap) erfolgt in den folgenden Schritten.

Fügen Sie das neue Element am Ende des Baums ein. Fügen Sie am Ende der Warteschlange ein Element ein
Haufen Sie den Baum. Nach dem Einfügen häufen

Algorithmus zum Einfügen eines Elements in die Prioritätswarteschlange (max-heap)

Wenn kein Knoten vorhanden ist, erstellen Sie einen neuen Knoten. Andernfalls (ein Knoten ist bereits vorhanden) fügen Sie den neuen Knoten am Ende ein (letzter Knoten von links nach rechts). Heapifizieren Sie das Array

Für Min Heap wird der obige Algorithmus so geändert, dass er parentNodeimmer kleiner als ist newNode.

2. Löschen eines Elements aus der Prioritätswarteschlange

Das Löschen eines Elements aus einer Prioritätswarteschlange (max-heap) erfolgt wie folgt:

Wählen Sie das zu löschende Element aus. Wählen Sie das zu löschende Element aus
Tauschen Sie es mit dem letzten Element aus. Mit dem letzten Blattknotenelement tauschen
Entfernen Sie das letzte Element. Entfernen Sie das letzte Elementblatt
Haufen Sie den Baum. Heapifizieren Sie die Prioritätswarteschlange

Algorithmus zum Löschen eines Elements in der Prioritätswarteschlange (max-heap)

 Wenn nodeToBeDeleted der leafNode ist, entfernen Sie den Knoten. Andernfalls tauschen Sie nodeToBeDeleted mit dem lastLeafNode. Entfernen Sie noteToBeDeleted, um das Array zu erhöhen

Für Min Heap wird der obige Algorithmus so geändert, dass beide childNodeskleiner als sind currentNode.

3. Spähen aus der Prioritätswarteschlange (Max / Min ermitteln)

Die Peek-Operation gibt das maximale Element von Max Heap oder das minimale Element von Min Heap zurück, ohne den Knoten zu löschen.

Für Max Heap und Min Heap

 return rootNode

4. Extrahieren Sie Max / Min aus der Prioritätswarteschlange

Extract-Max gibt den Knoten mit dem Maximalwert zurück, nachdem er aus einem Max-Heap entfernt wurde, während Extract-Min den Knoten mit dem Minimalwert zurückgibt, nachdem er aus dem Min-Heap entfernt wurde.

Implementierungen von Priority Queue in Python, Java, C und C ++

Python Java C C ++

 # Priority Queue implementation in Python # Function to heapify the tree def heapify(arr, n, i): # Find the largest among root, left child and right child largest = i l = 2 * i + 1 r = 2 * i + 2 if l < n and arr(i) < arr(l): largest = l if r < n and arr(largest) < arr(r): largest = r # Swap and continue heapifying if root is not largest if largest != i: arr(i), arr(largest) = arr(largest), arr(i) heapify(arr, n, largest) # Function to insert an element into the tree def insert(array, newNum): size = len(array) if size == 0: array.append(newNum) else: array.append(newNum) for i in range((size // 2) - 1, -1, -1): heapify(array, size, i) # Function to delete an element from the tree def deleteNode(array, num): size = len(array) i = 0 for i in range(0, size): if num == array(i): break array(i), array(size - 1) = array(size - 1), array(i) array.remove(size - 1) for i in range((len(array) // 2) - 1, -1, -1): heapify(array, len(array), i) arr = () insert(arr, 3) insert(arr, 4) insert(arr, 9) insert(arr, 5) insert(arr, 2) print ("Max-Heap array: " + str(arr)) deleteNode(arr, 4) print("After deleting an element: " + str(arr))

 // Priority Queue implementation in Java import java.util.ArrayList; class Heap ( // Function to heapify the tree void heapify(ArrayList hT, int i) ( int size = hT.size(); // Find the largest among root, left child and right child int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l hT.get(largest)) largest = l; if (r hT.get(largest)) largest = r; // Swap and continue heapifying if root is not largest if (largest != i) ( int temp = hT.get(largest); hT.set(largest, hT.get(i)); hT.set(i, temp); heapify(hT, largest); ) ) // Function to insert an element into the tree void insert(ArrayList hT, int newNum) ( int size = hT.size(); if (size == 0) ( hT.add(newNum); ) else ( hT.add(newNum); for (int i = size / 2 - 1; i>= 0; i--) ( heapify(hT, i); ) ) ) // Function to delete an element from the tree void deleteNode(ArrayList hT, int num) ( int size = hT.size(); int i; for (i = 0; i = 0; j--) ( heapify(hT, j); ) ) // Print the tree void printArray(ArrayList array, int size) ( for (Integer i : array) ( System.out.print(i + " "); ) System.out.println(); ) // Driver code public static void main(String args()) ( ArrayList array = new ArrayList(); int size = array.size(); Heap h = new Heap(); h.insert(array, 3); h.insert(array, 4); h.insert(array, 9); h.insert(array, 5); h.insert(array, 2); System.out.println("Max-Heap array: "); h.printArray(array, size); h.deleteNode(array, 4); System.out.println("After deleting an element: "); h.printArray(array, size); ) )

 // Priority Queue implementation in C #include int size = 0; void swap(int *a, int *b) ( int temp = *b; *b = *a; *a = temp; ) // Function to heapify the tree void heapify(int array(), int size, int i) ( if (size == 1) ( printf("Single element in the heap"); ) else ( // Find the largest among root, left child and right child int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l array(largest)) largest = l; if (r array(largest)) largest = r; // Swap and continue heapifying if root is not largest if (largest != i) ( swap(&array(i), &array(largest)); heapify(array, size, largest); ) ) ) // Function to insert an element into the tree void insert(int array(), int newNum) ( if (size == 0) ( array(0) = newNum; size += 1; ) else ( array(size) = newNum; size += 1; for (int i = size / 2 - 1; i>= 0; i--) ( heapify(array, size, i); ) ) ) // Function to delete an element from the tree void deleteRoot(int array(), int num) ( int i; for (i = 0; i  = 0; i--) ( heapify(array, size, i); ) ) // Print the array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) printf("%d ", array(i)); printf(""); ) // Driver code int main() ( int array(10); insert(array, 3); insert(array, 4); insert(array, 9); insert(array, 5); insert(array, 2); printf("Max-Heap array: "); printArray(array, size); deleteRoot(array, 4); printf("After deleting an element: "); printArray(array, size); )

 // Priority Queue implementation in C++ #include #include using namespace std; // Function to swap position of two elements void swap(int *a, int *b) ( int temp = *b; *b = *a; *a = temp; ) // Function to heapify the tree void heapify(vector &hT, int i) ( int size = hT.size(); // Find the largest among root, left child and right child int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l hT(largest)) largest = l; if (r hT(largest)) largest = r; // Swap and continue heapifying if root is not largest if (largest != i) ( swap(&hT(i), &hT(largest)); heapify(hT, largest); ) ) // Function to insert an element into the tree void insert(vector &hT, int newNum) ( int size = hT.size(); if (size == 0) ( hT.push_back(newNum); ) else ( hT.push_back(newNum); for (int i = size / 2 - 1; i>= 0; i--) ( heapify(hT, i); ) ) ) // Function to delete an element from the tree void deleteNode(vector &hT, int num) ( int size = hT.size(); int i; for (i = 0; i  = 0; i--) ( heapify(hT, i); ) ) // Print the tree void printArray(vector &hT) ( for (int i = 0; i < hT.size(); ++i) cout << hT(i) << " "; cout << ""; ) // Driver code int main() ( vector heapTree; insert(heapTree, 3); insert(heapTree, 4); insert(heapTree, 9); insert(heapTree, 5); insert(heapTree, 2); cout << "Max-Heap array: "; printArray(heapTree); deleteNode(heapTree, 4); cout << "After deleting an element: "; printArray(heapTree); )