Dans ce didacticiel, vous apprendrez ce qu'est la file d'attente prioritaire. Vous découvrirez également ses implémentations en Python, Java, C et C ++.
Une file d'attente prioritaire est un type spécial de file d'attente dans laquelle chaque élément est associé à une priorité et est servi en fonction de sa priorité. Si des éléments avec la même priorité apparaissent, ils sont servis selon leur ordre dans la file d'attente.
En général, la valeur de l'élément lui-même est prise en compte pour l'attribution de la priorité.
Par exemple, l'élément avec la valeur la plus élevée est considéré comme l'élément de priorité la plus élevée. Cependant, dans d'autres cas, nous pouvons supposer l'élément avec la valeur la plus basse comme élément de priorité la plus élevée. Dans d'autres cas, nous pouvons établir des priorités en fonction de nos besoins.
Suppression de l'élément de priorité la plus élevée
Différence entre la file d'attente prioritaire et la file d'attente normale
Dans une file d'attente, la règle du premier entré, premier sorti est implémentée alors que, dans une file d'attente prioritaire, les valeurs sont supprimées sur la base de la priorité . L'élément avec la priorité la plus élevée est supprimé en premier.
Implémentation de la file d'attente prioritaire
La file d'attente prioritaire peut être implémentée à l'aide d'un tableau, d'une liste liée, d'une structure de données de tas ou d'un arbre de recherche binaire. Parmi ces structures de données, la structure de données de tas fournit une implémentation efficace des files d'attente prioritaires.
Par conséquent, nous utiliserons la structure de données du tas pour implémenter la file d'attente prioritaire dans ce didacticiel. Un tas max est implémenté dans les opérations suivantes. Si vous voulez en savoir plus à ce sujet, veuillez visiter max-heap et mean-heap.
Une analyse comparative des différentes implémentations de la file d'attente prioritaire est donnée ci-dessous.
| Opérations | coup d'oeil | insérer | effacer |
|---|---|---|---|
| Liste liée | O(1) | O(n) | O(1) |
| Tas binaire | O(1) | O(log n) | O(log n) |
| Arbre de recherche binaire | O(1) | O(log n) | O(log n) |
Opérations de file d'attente prioritaires
Les opérations de base d'une file d'attente prioritaire sont l'insertion, la suppression et l'aperçu des éléments.
Avant d'étudier la file d'attente prioritaire, reportez-vous à la structure de données du tas pour une meilleure compréhension du tas binaire tel qu'il est utilisé pour implémenter la file d'attente prioritaire dans cet article.
1. Insertion d'un élément dans la file d'attente prioritaire
L'insertion d'un élément dans une file d'attente prioritaire (max-heap) se fait par les étapes suivantes.
- Insérez le nouvel élément à la fin de l'arborescence.
Insérer un élément à la fin de la file d'attente - Heapify l'arbre.
Heapify après insertion
Algorithme d'insertion d'un élément dans la file d'attente prioritaire (max-heap)
S'il n'y a pas de nœud, créez un nouveau nœud. else (un nœud est déjà présent) insérez le newNode à la fin (dernier nœud de gauche à droite.) heapify le tableau
Pour Min Heap, l'algorithme ci-dessus est modifié afin qu'il parentNodesoit toujours plus petit que newNode.
2. Suppression d'un élément de la file d'attente prioritaire
La suppression d'un élément d'une file d'attente prioritaire (max-heap) se fait comme suit:
- Sélectionnez l'élément à supprimer.
Sélectionnez l'élément à supprimer - Échangez-le avec le dernier élément.
Échange avec le dernier élément de nœud feuille - Supprimez le dernier élément.
Supprimer la dernière feuille d'élément - Heapify l'arbre.
Heapify la file d'attente prioritaire
Algorithme de suppression d'un élément dans la file d'attente prioritaire (max-heap)
Si nodeToBeDeleted est le leafNode supprimer le nœud Sinon swap nodeToBeDeleted avec le lastLeafNode remove noteToBeDeleted heapify le tableau
Pour Min Heap, l'algorithme ci-dessus est modifié afin que les deux childNodessoient plus petits que currentNode.
3. Peeking from the Priority Queue (Trouver max / min)
L'opération Peek renvoie l'élément maximum de Max Heap ou l'élément minimum de Min Heap sans supprimer le nœud.
Pour les tas Max et Min Heap
retourner rootNode
4. Extraire-Max / Min de la file d'attente prioritaire
Extract-Max renvoie le nœud avec la valeur maximale après l'avoir supprimé d'un tas Max tandis que Extract-Min renvoie le nœud avec la valeur minimale après l'avoir supprimé du tas min.
Implémentations de file d'attente prioritaire en Python, Java, C et 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); )
Applications de file d'attente prioritaires
Certaines des applications d'une file d'attente prioritaire sont:
- Algorithme de Dijkstra
- pour implémenter la pile
- pour l'équilibrage de charge et la gestion des interruptions dans un système d'exploitation
- pour la compression de données dans le code Huffman
