In deze zelfstudie leert u wat de prioriteitswachtrij is. Je leert ook over de implementaties ervan in Python, Java, C en C ++.
Een prioriteitswachtrij is een speciaal type wachtrij waarin elk element is gekoppeld aan een prioriteit en wordt bediend volgens zijn prioriteit. Als elementen met dezelfde prioriteit voorkomen, worden ze op volgorde in de wachtrij geserveerd.
Over het algemeen wordt bij het toekennen van de prioriteit rekening gehouden met de waarde van het element zelf.
Het element met de hoogste waarde wordt bijvoorbeeld beschouwd als element met de hoogste prioriteit. In andere gevallen kunnen we echter aannemen dat het element met de laagste waarde het element met de hoogste prioriteit heeft. In andere gevallen kunnen we prioriteiten stellen op basis van onze behoeften.
Element met hoogste prioriteit verwijderen
Verschil tussen prioriteitswachtrij en normale wachtrij
In een wachtrij wordt de first-in-first-out-regel geïmplementeerd, terwijl in een prioriteitswachtrij de waarden worden verwijderd op basis van prioriteit . Het element met de hoogste prioriteit wordt als eerste verwijderd.
Implementatie van prioriteitswachtrij
Prioriteitswachtrij kan worden geïmplementeerd met behulp van een array, een gekoppelde lijst, een heap-gegevensstructuur of een binaire zoekboom. Onder deze datastructuren biedt heap-datastructuur een efficiënte implementatie van prioriteitswachtrijen.
Daarom zullen we de heap-gegevensstructuur gebruiken om de prioriteitswachtrij in deze zelfstudie te implementeren. Een max-heap is implement in de volgende bewerkingen. Als je er meer over wilt weten, bezoek dan max-heap en mean-heap.
Een vergelijkende analyse van verschillende implementaties van prioriteitswachtrij wordt hieronder gegeven.
| Operaties | kijkje | invoegen | verwijderen |
|---|---|---|---|
| Gekoppelde lijst | O(1) | O(n) | O(1) |
| Binaire hoop | O(1) | O(log n) | O(log n) |
| Binaire zoekboom | O(1) | O(log n) | O(log n) |
Prioritaire wachtrijbewerkingen
Basisbewerkingen van een prioriteitswachtrij zijn het invoegen, verwijderen en bekijken van elementen.
Voordat u de prioriteitswachtrij bestudeert, raadpleegt u de heap-gegevensstructuur voor een beter begrip van de binaire heap zoals deze wordt gebruikt om de prioriteitswachtrij in dit artikel te implementeren.
1. Een element in de prioriteitswachtrij invoegen
Het invoegen van een element in een prioriteitswachtrij (max-heap) wordt gedaan door de volgende stappen.
- Voeg het nieuwe element aan het einde van de boom toe.
Voeg een element in aan het einde van de wachtrij - Heapify de boom.
Heapify na inbrengen
Algoritme voor het invoegen van een element in de prioriteitswachtrij (max-heap)
Als er geen knooppunt is, maakt u een newNode. anders (een knoop is al aanwezig) plaats de nieuwe knoop aan het einde (laatste knooppunt van links naar rechts.) heapify de array
Voor Min Heap is het bovenstaande algoritme aangepast zodat het parentNodealtijd kleiner is dan newNode.
2. Een element verwijderen uit de prioriteitswachtrij
Het verwijderen van een element uit een prioriteitswachtrij (max-heap) gaat als volgt:
- Selecteer het element dat u wilt verwijderen.
Selecteer het element dat u wilt verwijderen - Verwissel het met het laatste element.
Wissel met het laatste bladknooppuntelement - Verwijder het laatste element.
Verwijder het laatste elementblad - Heapify de boom.
Heapify de prioriteitswachtrij
Algoritme voor het verwijderen van een element in de prioriteitswachtrij (max-heap)
Als nodeToBeDeleted de leafNode is, verwijder dan het knooppunt. Anders verwissel nodeToBeDeleted met de lastLeafNode remove noteToBeDeleted heapify de array
Voor Min Heap is het bovenstaande algoritme aangepast zodat beide childNodeskleiner zijn dan currentNode.
3. Gluren vanuit de prioriteitswachtrij (max / min zoeken)
De Peek-bewerking retourneert het maximumelement uit Max Heap of minimumelement uit Min Heap zonder het knooppunt te verwijderen.
Voor zowel Max heap als Min Heap
retourneer rootNode
4. Extract-Max / Min uit de prioriteitswachtrij
Extract-Max retourneert het knooppunt met de maximale waarde nadat het uit een Max Heap is verwijderd, terwijl Extract-Min het knooppunt met de minimale waarde retourneert nadat het uit de Min Heap is verwijderd.
Prioriteitswachtrij-implementaties in Python, Java, C en 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); )
Prioritaire wachtrijtoepassingen
Enkele van de toepassingen van een prioriteitswachtrij zijn:
- Dijkstra's algoritme
- voor het implementeren van stack
- voor taakverdeling en afhandeling van onderbrekingen in een besturingssysteem
- voor datacompressie in Huffman-code
