UN File d'attente de priorité est un type de file d'attente qui organise les éléments en fonction de leurs valeurs de priorité. Les éléments ayant des valeurs de priorité plus élevées sont généralement récupérés avant les éléments ayant des valeurs de priorité plus faibles.
Dans une file d'attente prioritaire, chaque élément est associé à une valeur de priorité. Lorsque vous ajoutez un élément à la file d'attente, il est inséré à une position en fonction de sa valeur de priorité. Par exemple, si vous ajoutez un élément avec une valeur de priorité élevée à une file d'attente prioritaire, il peut être inséré près du début de la file d'attente, tandis qu'un élément avec une valeur de priorité faible peut être inséré près de l'arrière.
Il existe plusieurs façons d'implémenter une file d'attente prioritaire, notamment en utilisant un tableau, une liste chaînée, un tas ou un arbre de recherche binaire. Chaque méthode a ses propres avantages et inconvénients, et le meilleur choix dépendra des besoins spécifiques de votre application.
Les files d'attente prioritaires sont souvent utilisées dans les systèmes en temps réel, où l'ordre dans lequel les éléments sont traités peut avoir des conséquences importantes. Ils sont également utilisés dans les algorithmes pour améliorer leur efficacité, comme L'algorithme de Dijkstra pour trouver le chemin le plus court dans un graphique et l'algorithme de recherche A* pour la recherche de chemin.
Propriétés de la file d'attente prioritaire
Ainsi, une file d'attente prioritaire est une extension de la file d'attente avec les propriétés suivantes.
- Chaque élément est associé à une priorité.
- Un élément de priorité élevée est retiré de la file d'attente avant un élément de priorité faible.
- Si deux éléments ont la même priorité, ils sont servis selon leur ordre dans la file d'attente.
Dans la file d'attente prioritaire ci-dessous, un élément avec une valeur ASCII maximale aura la priorité la plus élevée. Les éléments ayant une priorité plus élevée sont servis en premier.
Comment la priorité est-elle attribuée aux éléments d’une file d’attente prioritaire ?
Dans une file d'attente prioritaire, généralement, la valeur d'un élément est prise en compte pour attribuer la priorité.
Par exemple, l'élément ayant la valeur la plus élevée se voit attribuer la priorité la plus élevée et l'élément ayant la valeur la plus faible se voit attribuer la priorité la plus basse. Le cas inverse peut également être utilisé, c'est-à-dire que l'élément avec la valeur la plus basse peut se voir attribuer la priorité la plus élevée. De plus, la priorité peut être attribuée selon nos besoins.
Opérations d'une file d'attente prioritaire :
Une file d'attente prioritaire typique prend en charge les opérations suivantes :
1) Insertion dans une file d'attente prioritaire
Lorsqu'un nouvel élément est inséré dans une file d'attente prioritaire, il se déplace vers l'emplacement vide de haut en bas et de gauche à droite. Cependant, si l’élément n’est pas au bon endroit alors il sera comparé au nœud parent. Si l'élément n'est pas dans le bon ordre, les éléments sont échangés. Le processus d'échange se poursuit jusqu'à ce que tous les éléments soient placés dans la bonne position.
2) Suppression dans une file d'attente prioritaire
Comme vous le savez, dans un tas max, l'élément maximum est le nœud racine. Et cela supprimera en premier l’élément qui a la priorité maximale. Ainsi, vous supprimez le nœud racine de la file d'attente. Cette suppression crée un emplacement vide, qui sera ensuite rempli par une nouvelle insertion. Ensuite, il compare l'élément nouvellement inséré avec tous les éléments de la file d'attente pour maintenir le tas invariant.
3) Jetez un œil dans une file d’attente prioritaire
Cette opération permet de renvoyer l'élément maximum de Max Heap ou l'élément minimum de Min Heap sans supprimer le nœud de la file d'attente prioritaire.
Types de file d'attente prioritaire :
1) File d’attente prioritaire par ordre croissant
Comme son nom l'indique, dans la file d'attente prioritaire par ordre croissant, l'élément avec une valeur de priorité inférieure reçoit une priorité plus élevée dans la liste des priorités. Par exemple, si nous avons les éléments suivants dans une file d'attente prioritaire classés par ordre croissant comme 4,6,8,9,10. Ici, 4 est le plus petit nombre, par conséquent, il obtiendra la priorité la plus élevée dans une file d'attente prioritaire et ainsi, lorsque nous retirerons de la file d'attente de ce type de file d'attente prioritaire, 4 sera supprimé de la file d'attente et retiré de la file d'attente renvoie 4.
2) File d'attente prioritaire par ordre décroissant
Le nœud racine est l'élément maximum dans un tas maximum, comme vous le savez peut-être. Cela supprimera également en premier l’élément ayant la priorité la plus élevée. En conséquence, le nœud racine est supprimé de la file d'attente. Cette suppression laisse un espace vide, qui sera rempli par de nouvelles insertions dans le futur. L'invariant du tas est ensuite maintenu en comparant l'élément nouvellement inséré à toutes les autres entrées de la file d'attente.
Types de files d'attente prioritaires
Différence entre la file d'attente prioritaire et la file d'attente normale ?
Il n'y a pas de priorité attachée aux éléments dans une file d'attente, la règle du premier entré, premier sorti (FIFO) est implémentée alors que, dans une file d'attente prioritaire, les éléments ont une priorité. Les éléments ayant une priorité plus élevée sont servis en premier.
Comment implémenter une file d’attente prioritaire ?
La file d'attente prioritaire peut être implémentée à l'aide des structures de données suivantes :
- Tableaux
- Liste chaînée
- Structure de données de tas
- Arbre de recherche binaire
Discutons de tout cela en détail.
1) Implémenter la file d'attente prioritaire à l'aide d'un tableau :
Une implémentation simple consiste à utiliser un tableau de la structure suivante.
élément de structure {
article entier ;
priorité int ;
}
- enqueue() : Cette fonction est utilisée pour insérer de nouvelles données dans la file d'attente. dequeue() : Cette fonction supprime de la file d'attente l'élément ayant la priorité la plus élevée. peek()/top() : Cette fonction est utilisée pour obtenir l'élément de priorité la plus élevée dans la file d'attente sans le supprimer de la file d'attente.
| Tableaux | mettre en file d'attente() | par conséquent () | coup d'oeil() |
|---|---|---|---|
| Complexité temporelle | O(1) | Sur) cours de mathématiques Java | Sur) |
C++
// C++ program to implement Priority Queue> // using Arrays> #include> using> namespace> std;> // Structure for the elements in the> // priority queue> struct> item {> >int> value;> >int> priority;> };> // Store the element of a priority queue> item pr[100000];> // Pointer to the last index> int> size = -1;> // Function to insert a new element> // into priority queue> void> enqueue(>int> value,>int> priority)> {> >// Increase the size> >size++;> >// Insert the element> >pr[size].value = value;> >pr[size].priority = priority;> }> // Function to check the top element> int> peek()> {> >int> highestPriority = INT_MIN;> >int> ind = -1;> >// Check for the element with> >// highest priority> >for> (>int> i = 0; i <= size; i++) {> >// If priority is same choose> >// the element with the> >// highest value> >if> (highestPriority == pr[i].priority && ind>-1> >&& pr[ind].value highestPriority = pr[i].priority; ind = i; } else if (highestPriority highestPriority = pr[i].priority; ind = i; } } // Return position of the element return ind; } // Function to remove the element with // the highest priority void dequeue() { // Find the position of the element // with highest priority int ind = peek(); // Shift the element one index before // from the position of the element // with highest priority is found for (int i = ind; i pr[i] = pr[i + 1]; } // Decrease the size of the // priority queue by one size--; } // Driver Code int main() { // Function Call to insert elements // as per the priority enqueue(10, 2); enqueue(14, 4); enqueue(16, 4); enqueue(12, 3); // Stores the top element // at the moment int ind = peek(); cout << pr[ind].value << endl; // Dequeue the top element dequeue(); // Check the top element ind = peek(); cout << pr[ind].value << endl; // Dequeue the top element dequeue(); // Check the top element ind = peek(); cout << pr[ind].value << endl; return 0; }> |
>
>
Java
// Java program to implement Priority Queue> // using Arrays> import> java.util.*;> // Structure for the elements in the> // priority queue> class> item {> >public> int> value;> >public> int> priority;> };> class> GFG {> >// Store the element of a priority queue> >static> item[] pr =>new> item[>100000>];> >// Pointer to the last index> >static> int> size = ->1>;> >// Function to insert a new element> >// into priority queue> >static> void> enqueue(>int> value,>int> priority)> >{> >// Increase the size> >size++;> >// Insert the element> >pr[size] =>new> item();> >pr[size].value = value;> >pr[size].priority = priority;> >}> >// Function to check the top element> >static> int> peek()> >{> >int> highestPriority = Integer.MIN_VALUE;> >int> ind = ->1>;> >// Check for the element with> >// highest priority> >for> (>int> i =>0>; i <= size; i++) {> >// If priority is same choose> >// the element with the> >// highest value> >if> (highestPriority == pr[i].priority> >&& ind>->1> >&& pr[ind].value highestPriority = pr[i].priority; ind = i; } else if (highestPriority highestPriority = pr[i].priority; ind = i; } } // Return position of the element return ind; } // Function to remove the element with // the highest priority static void dequeue() { // Find the position of the element // with highest priority int ind = peek(); // Shift the element one index before // from the position of the element // with highest priority is found for (int i = ind; i pr[i] = pr[i + 1]; } // Decrease the size of the // priority queue by one size--; } public static void main(String[] args) { // Function Call to insert elements // as per the priority enqueue(10, 2); enqueue(14, 4); enqueue(16, 4); enqueue(12, 3); // Stores the top element // at the moment int ind = peek(); System.out.println(pr[ind].value); // Dequeue the top element dequeue(); // Check the top element ind = peek(); System.out.println(pr[ind].value); // Dequeue the top element dequeue(); // Check the top element ind = peek(); System.out.println(pr[ind].value); } } // this code is contributed by phasing17> |
>
>
Python3
import> sys> # Structure for the elements in the> # priority queue> class> item :> >value>=> 0> >priority>=> 0> class> GFG :> > ># Store the element of a priority queue> >pr>=> [>None>]>*> (>100000>)> > ># Pointer to the last index> >size>=> ->1> > ># Function to insert a new element> ># into priority queue> >@staticmethod> >def> enqueue( value, priority) :> > ># Increase the size> >GFG.size>+>=> 1> > ># Insert the element> >GFG.pr[GFG.size]>=> item()> >GFG.pr[GFG.size].value>=> value> >GFG.pr[GFG.size].priority>=> priority> > ># Function to check the top element> >@staticmethod> >def> peek() :> >highestPriority>=> ->sys.maxsize> >ind>=> ->1> > ># Check for the element with> ># highest priority> >i>=> 0> >while> (i <>=> GFG.size) :> > ># If priority is same choose> ># the element with the> ># highest value> >if> (highestPriority>=>=> GFG.pr[i].priority>and> ind>>->1> and> GFG.pr[ind].value highestPriority = GFG.pr[i].priority ind = i elif(highestPriority highestPriority = GFG.pr[i].priority ind = i i += 1 # Return position of the element return ind # Function to remove the element with # the highest priority @staticmethod def dequeue() : # Find the position of the element # with highest priority ind = GFG.peek() # Shift the element one index before # from the position of the element # with highest priority is found i = ind while (i GFG.pr[i] = GFG.pr[i + 1] i += 1 # Decrease the size of the # priority queue by one GFG.size -= 1 @staticmethod def main( args) : # Function Call to insert elements # as per the priority GFG.enqueue(10, 2) GFG.enqueue(14, 4) GFG.enqueue(16, 4) GFG.enqueue(12, 3) # Stores the top element # at the moment ind = GFG.peek() print(GFG.pr[ind].value) # Dequeue the top element GFG.dequeue() # Check the top element ind = GFG.peek() print(GFG.pr[ind].value) # Dequeue the top element GFG.dequeue() # Check the top element ind = GFG.peek() print(GFG.pr[ind].value) if __name__=='__main__': GFG.main([]) # This code is contributed by aadityaburujwale.> |
>
>
C#
// C# program to implement Priority Queue> // using Arrays> using> System;> // Structure for the elements in the> // priority queue> public> class> item {> >public> int> value;> >public> int> priority;> };> public> class> GFG> {> > >// Store the element of a priority queue> >static> item[] pr =>new> item[100000];> >// Pointer to the last index> >static> int> size = -1;> >// Function to insert a new element> >// into priority queue> >static> void> enqueue(>int> value,>int> priority)> >{> >// Increase the size> >size++;> > >// Insert the element> >pr[size] =>new> item();> >pr[size].value = value;> >pr[size].priority = priority;> >}> > >// Function to check the top element> >static> int> peek()> >{> >int> highestPriority =>int>.MinValue;> >int> ind = -1;> > >// Check for the element with> >// highest priority> >for> (>int> i = 0; i <= size; i++) {> > >// If priority is same choose> >// the element with the> >// highest value> >if> (highestPriority == pr[i].priority && ind>-1> >&& pr[ind].value highestPriority = pr[i].priority; ind = i; } else if (highestPriority highestPriority = pr[i].priority; ind = i; } } // Return position of the element return ind; } // Function to remove the element with // the highest priority static void dequeue() { // Find the position of the element // with highest priority int ind = peek(); // Shift the element one index before // from the position of the element // with highest priority is found for (int i = ind; i pr[i] = pr[i + 1]; } // Decrease the size of the // priority queue by one size--; } public static void Main(string[] args) { // Function Call to insert elements // as per the priority enqueue(10, 2); enqueue(14, 4); enqueue(16, 4); enqueue(12, 3); // Stores the top element // at the moment int ind = peek(); Console.WriteLine(pr[ind].value); // Dequeue the top element dequeue(); // Check the top element ind = peek(); Console.WriteLine(pr[ind].value); // Dequeue the top element dequeue(); // Check the top element ind = peek(); Console.WriteLine(pr[ind].value); } } //this code is contributed by phasing17> |
>
>
Javascript
// JavaScript program to implement Priority Queue> // using Arrays> // Structure for the elements in the> // priority queue> class item {> >constructor()> >{> >this>.value;> >this>.priority;> >}> };> // Store the element of a priority queue> let pr = [];> for> (>var> i = 0; i <100000; i++)> >pr.push(>new> item());> // Pointer to the last index> let size = -1;> // Function to insert a new element> // into priority queue> function> enqueue(value, priority)> {> >// Increase the size> >size++;> >// Insert the element> >pr[size] =>new> item();> >pr[size].value = value;> >pr[size].priority = priority;> }> // Function to check the top element> function> peek()> {> >let highestPriority = Number.MIN_SAFE_INTEGER;> >let ind = -1;> >// Check for the element with> >// highest priority> >for> (>var> i = 0; i <= size; i++) {> >// If priority is same choose> >// the element with the> >// highest value> >if> (highestPriority == pr[i].priority && ind>-1> >&& pr[ind].value highestPriority = pr[i].priority; ind = i; } else if (highestPriority highestPriority = pr[i].priority; ind = i; } } // Return position of the element return ind; } // Function to remove the element with // the highest priority function dequeue() { // Find the position of the element // with highest priority let ind = peek(); // Shift the element one index before // from the position of the element // with highest priority is found for (var i = ind; i pr[i] = pr[i + 1]; } // Decrease the size of the // priority queue by one size--; } // Function Call to insert elements // as per the priority enqueue(10, 2); enqueue(14, 4); enqueue(16, 4); enqueue(12, 3); // Stores the top element // at the moment let ind = peek(); console.log(pr[ind].value); // Dequeue the top element dequeue(); // Check the top element ind = peek(); console.log(pr[ind].value); // Dequeue the top element dequeue(); // Check the top element ind = peek(); console.log(pr[ind].value); // this code is contributed by phasing17> |
>
>Sortir
16 14 12>
Note: Lire Cet article pour plus de détails.
2) Implémenter la file d'attente prioritaire à l'aide d'une liste chaînée :
Dans une implémentation LinkedList, les entrées sont triées par ordre décroissant en fonction de leur priorité. L'élément ayant la priorité la plus élevée est toujours ajouté au début de la file d'attente prioritaire, qui est formée à l'aide de listes chaînées. Les fonctions comme pousser() , populaire() , et coup d'oeil() sont utilisés pour implémenter une file d'attente prioritaire à l'aide d'une liste chaînée et sont expliqués comme suit :
- push() : Cette fonction est utilisée pour insérer de nouvelles données dans la file d'attente. pop() : Cette fonction supprime l'élément ayant la priorité la plus élevée de la file d'attente. peek() / top() : Cette fonction est utilisée pour obtenir l'élément de priorité la plus élevée dans la file d'attente sans le supprimer de la file d'attente.
| Liste liée télécharger des vidéos YouTube avec VLC | pousser() | populaire() | coup d'oeil() |
|---|---|---|---|
| Complexité temporelle | Sur) | O(1) | O(1) |
C++
// C++ code to implement Priority Queue> // using Linked List> #include> using> namespace> std;> // Node> typedef> struct> node {> >int> data;> >// Lower values indicate> >// higher priority> >int> priority;> >struct> node* next;> } Node;> // Function to create a new node> Node* newNode(>int> d,>int> p)> {> >Node* temp = (Node*)>malloc>(>sizeof>(Node));> >temp->données = d;> >temp->priorité = p;> >temp->suivant = NULL;> >return> temp;> }> // Return the value at head> int> peek(Node** head) {>return> (*head)->données; }> // Removes the element with the> // highest priority form the list> void> pop(Node** head)> {> >Node* temp = *head;> >(*head) = (*head)->suivant;> >free>(temp);> }> // Function to push according to priority> void> push(Node** head,>int> d,>int> p)> {> >Node* start = (*head);> >// Create new Node> >Node* temp = newNode(d, p);> >// Special Case: The head of list has> >// lesser priority than new node> >if> ((*head)->priorité // Insérer un nouveau nœud avant head temp->next = *head; (*tête) = temp; } else { // Parcourez la liste et trouvez // une position pour insérer un nouveau nœud while (start->next != NULL && start->next->priority> p) { start = start->next; } // Soit aux extrémités de la liste // soit à la position requise temp->next = start->next; début->suivant = temp; } } // La fonction pour vérifier si la liste est vide int isEmpty(Node** head) { return (*head) == NULL; } // Code du pilote int main() { // Créer une file d'attente prioritaire // 7->4->5->6 Node* pq = newNode(4, 1); pousser(&pq, 5, 2); pousser(&pq, 6, 3); pousser(&pq, 7, 0); while (!isEmpty(&pq)) { cout<< ' ' << peek(&pq); pop(&pq); } return 0; }> |
>
>
Java
// Java code to implement Priority Queue> // using Linked List> import> java.util.* ;> class> Solution> {> // Node> static> class> Node {> >int> data;> > >// Lower values indicate higher priority> >int> priority;> >Node next;> > }> static> Node node =>new> Node();> > // Function to Create A New Node> static> Node newNode(>int> d,>int> p)> {> >Node temp =>new> Node();> >temp.data = d;> >temp.priority = p;> >temp.next =>null>;> > >return> temp;> }> > // Return the value at head> static> int> peek(Node head)> {> >return> (head).data;> }> > // Removes the element with the> // highest priority from the list> static> Node pop(Node head)> {> >Node temp = head;> >(head) = (head).next;> >return> head;> }> > // Function to push according to priority> static> Node push(Node head,>int> d,>int> p)> {> >Node start = (head);> > >// Create new Node> >Node temp = newNode(d, p);> > >// Special Case: The head of list has lesser> >// priority than new node. So insert new> >// node before head node and change head node.> >if> ((head).priority // Insert New Node before head temp.next = head; (head) = temp; } else { // Traverse the list and find a // position to insert new node while (start.next != null && start.next.priority>p) { start = start.next ; } // Soit aux extrémités de la liste // soit à la position requise temp.next = start.next; start.next = temp; } retourne la tête ; } // La fonction pour vérifier si la liste est vide static int isEmpty(Node head) { return ((head) == null)?1:0; } // Code du pilote public static void main(String args[]) { // Créer une file d'attente prioritaire // 7.4.5.6 Noeud pq = newNode(4, 1); pq = pousser (pq, 5, 2); pq = pousser (pq, 6, 3); pq = pousser (pq, 7, 0); while (isEmpty(pq)==0) { System.out.printf('%d ', peek(pq)); pq=pop(pq); } } } // Ce code est fourni par ishankhandelwals.> |
>
>
Python
# Python3 code to implement Priority Queue> # using Singly Linked List> # Class to create new node which includes> # Node Data, and Node Priority> class> PriorityQueueNode:> >def> _init_(>self>, value, pr):> >self>.data>=> value> >self>.priority>=> pr> >self>.>next> => None> # Implementation of Priority Queue> class> PriorityQueue:> >def> _init_(>self>):> >self>.front>=> None> ># Method to check Priority Queue is Empty> ># or not if Empty then it will return True> ># Otherwise False> >def> isEmpty(>self>):> >return> True> if> self>.front>=>=> None> else> False> ># Method to add items in Priority Queue> ># According to their priority value> >def> push(>self>, value, priority):> ># Condition check for checking Priority> ># Queue is empty or not> >if> self>.isEmpty()>=>=> True>:> ># Creating a new node and assigning> ># it to class variable> >self>.front>=> PriorityQueueNode(value,> >priority)> ># Returning 1 for successful execution> >return> 1> >else>:> ># Special condition check to see that> ># first node priority value> >if> self>.front.priority # Creating a new node newNode = PriorityQueueNode(value, priority) # Updating the new node next value newNode.next = self.front # Assigning it to self.front self.front = newNode # Returning 1 for successful execution return 1 else: # Traversing through Queue until it # finds the next smaller priority node temp = self.front while temp.next: # If same priority node found then current # node will come after previous node if priority>= temp.next.priority: break temp = temp.next newNode = PriorityQueueNode(value, priorité) newNode.next = temp.next temp.next = newNode # Renvoi de 1 pour une exécution réussie, retour 1 # Méthode pour supprimer l'élément de haute priorité # de la file d'attente prioritaire def pop(self): # Vérification des conditions pour vérifier # La file d'attente prioritaire est vide ou non si self.isEmpty() == True : return else: # Suppression du nœud haute priorité de # la file d'attente prioritaire et mise à jour du front # avec next node self.front = self.front.next return 1 # Méthode pour renvoyer un nœud haute priorité # value Ne pas le supprimer def peek(self): # Vérification des conditions pour vérifier la priorité # La file d'attente est vide ou non si self.isEmpty() == True : return else : return self.front.data # Méthode pour parcourir la priorité # File d'attente def traverse(self) : # Vérification des conditions pour vérifier la priorité # La file d'attente est vide ou non si self.isEmpty() == True : return ' La file d'attente est vide !' else : temp = self.front while temp: print(temp.data, end=' ') temp = temp.next # Code du pilote si _name_ == '_main_' : # Création d'un instance de Priority # Queue, et en ajoutant les valeurs # 7 -> 4 -> 5 -> 6 pq = PriorityQueue() pq.push(4, 1) pq.push(5, 2) pq.push(6, 3) pq .push(7, 0) # Traversée de la file d'attente prioritaire pq.traverse() # Suppression de l'élément de priorité la plus élevée # pour la file d'attente prioritaire pq.pop()> |
>
>
C#
// C# code to implement Priority Queue> // using Linked List> using> System;> class> GFG> {> >// Node> >public> class> Node> >{> >public> int> data;> >// Lower values indicate> >// higher priority> >public> int> priority;> >public> Node next;> >}> >public> static> Node node =>new> Node();> >// Function to Create A New Node> >public> static> Node newNode(>int> d,>int> p)> >{> >Node temp =>new> Node();> >temp.data = d;> >temp.priority = p;> >temp.next =>null>;> >return> temp;> >}> >// Return the value at head> >public> static> int> peek(Node head)> >{> >return> (head).data;> >}> >// Removes the element with the> >// highest priority from the list> >public> static> Node pop(Node head)> >{> >Node temp = head;> >(head) = (head).next;> >return> head;> >}> >// Function to push according to priority> >public> static> Node push(Node head,> >int> d,>int> p)> >{> >Node start = (head);> >// Create new Node> >Node temp = newNode(d, p);> >// Special Case: The head of list> >// has lesser priority than new node.> >// So insert new node before head node> >// and change head node.> >if> ((head).priority { // Insert New Node before head temp.next = head; (head) = temp; } else { // Traverse the list and find a // position to insert new node while (start.next != null && start.next.priority>p) { start = start.next ; } // Soit aux extrémités de la liste // soit à la position requise temp.next = start.next; start.next = temp; } retourne la tête ; } // La fonction pour vérifier si la liste est vide public static int isEmpty(Node head) { return ((head) == null) ? dix; } // Code du pilote public static void Main(string[] args) { // Créer une file d'attente prioritaire // 7.4.5.6 Noeud pq = newNode(4, 1); pq = pousser(pq, 5, 2); pq = pousser(pq, 6, 3); pq = pousser(pq, 7, 0); while (isEmpty(pq) == 0) { Console.Write('{0:D} ', peek(pq)); pq = pop(pq); } } } // Ce code est fourni par ishankhandelwals.> |
>
>
Javascript
// JavaScript code to implement Priority Queue> // using Linked List> // Node> class Node {> >// Lower values indicate> >// higher priority> >constructor() {> >this>.data = 0;> >this>.priority = 0;> >this>.next =>null>;> >}> }> var> node =>new> Node();> // Function to Create A New Node> function> newNode(d, p) {> >var> temp =>new> Node();> >temp.data = d;> >temp.priority = p;> >temp.next =>null>;> >return> temp;> }> // Return the value at head> function> peek(head) {> >return> head.data;> }> // Removes the element with the> // highest priority from the list> function> pop(head) {> >var> temp = head;> >head = head.next;> >return> head;> }> // Function to push according to priority> function> push(head, d, p) {> >var> start = head;> >// Create new Node> >var> temp = newNode(d, p);> >// Special Case: The head of list> >// has lesser priority than new node.> >// So insert new node before head node> >// and change head node.> >if> (head.priority // Insert New Node before head temp.next = head; head = temp; } else { // Traverse the list and find a // position to insert new node while (start.next != null && start.next.priority>p) { start = start.next ; } // Soit aux extrémités de la liste // soit à la position requise temp.next = start.next; start.next = temp; } retourne la tête ; } // La fonction pour vérifier si la liste est vide function isEmpty(head) { return head == null ? dix; } // Code du pilote // Créer une file d'attente prioritaire // 7.4.5.6 var pq = newNode(4, 1); pq = pousser(pq, 5, 2); pq = pousser(pq, 6, 3); pq = pousser(pq, 7, 0); while (isEmpty(pq) == 0) { console.log(peek(pq),' '); pq = pop(pq); } // Ce code est fourni par ishankhandelwals.> |
>
>Sortir
6 5 4 7>
Reportez-vous à cet article pour plus de détails.
Note: Nous pouvons également utiliser la liste chaînée, la complexité temporelle de toutes les opérations avec la liste chaînée reste la même que celle du tableau. L'avantage de la liste chaînée est supprimerHighestPriority() peut être plus efficace car nous n’avons pas besoin de déplacer d’éléments.
3) Implémenter la file d'attente prioritaire à l'aide de tas :
Binary Heap est généralement préféré pour l'implémentation de files d'attente prioritaires, car les tas offrent de meilleures performances par rapport aux tableaux ou à LinkedList. Compte tenu des propriétés d'un tas, l'entrée avec la plus grande clé se trouve en haut et peut être supprimée immédiatement. Il faudra cependant du temps O(log n) pour restaurer la propriété du tas pour les clés restantes. Cependant, si une autre entrée doit être insérée immédiatement, alors une partie de ce temps peut être combinée avec le temps O(log n) nécessaire pour insérer la nouvelle entrée. Ainsi, la représentation d'une file d'attente prioritaire sous forme de tas s'avère avantageuse pour n grand, car elle est représentée efficacement dans un stockage contigu et il est garanti qu'elle ne nécessite qu'un temps logarithmique pour les insertions et les suppressions. Les opérations sur le tas binaire sont les suivantes :
- insert(p) : Insère un nouvel élément avec la priorité p. extractMax() : extrait un élément avec une priorité maximale. Remove(i) : Supprime un élément pointé par un itérateur i. getMax() : renvoie un élément avec une priorité maximale. changePriority(i, p) : Change la priorité d'un élément pointé par je à p .
| Tas binaire | insérer() | retirer() | coup d'oeil() |
|---|---|---|---|
| Complexité temporelle | O (log n) | O (log n) | O(1) |
Reportez-vous à cet article pour l'implémentation du code.
4) Implémenter la file d'attente prioritaire à l'aide de l'arborescence de recherche binaire :
Un arbre de recherche binaire auto-équilibré comme l'arbre AVL, l'arbre rouge-noir, etc. peut également être utilisé pour implémenter une file d'attente prioritaire. Des opérations telles que peek(), insert() et delete() peuvent être effectuées en utilisant BST.
| Arbre de recherche binaire | coup d'oeil() | insérer() | supprimer() |
|---|---|---|---|
| Complexité temporelle | O(1) | O (log n) | O (log n) |
Applications de la file d'attente prioritaire :
- Planification du processeur
- Algorithmes graphiques comme l'algorithme du chemin le plus court de Dijkstra, l'arbre couvrant minimum de Prim, etc.
- Implémentation de la pile
- Toutes les applications de la file d'attente prioritaire
- File d'attente prioritaire en C++
- File d'attente prioritaire en Java
- File d'attente prioritaire en Python
- File d'attente prioritaire en JavaScript
- Articles récents sur la file d'attente prioritaire !