priority queue data structure c with illustration
Introduction à la file d'attente prioritaire en C ++ avec illustration.
Priority Queue est une extension de la file d'attente dont nous avons parlé dans notre dernier tutoriel.
Elle est similaire à la file d'attente dans certains aspects et pourtant elle diffère de la file d'attente ordinaire sur les points suivants:
- Chaque élément de la file d'attente prioritaire est associé à une priorité.
- L'élément avec la priorité la plus élevée est le premier élément à être supprimé de la file d'attente.
- Si plusieurs éléments ont la même priorité, leur ordre dans la file d'attente est pris en compte.
=> Cliquez ici pour la série de formations Absolute C ++.
Nous pouvons visualiser la file d'attente prioritaire comme une version modifiée de la file d'attente, sauf que lorsque l'élément doit être retiré de la file d'attente, l'élément avec la priorité la plus élevée est récupéré en premier. Nous préférons donc utiliser les files d'attente prioritaires au lieu des files d'attente lorsque nous devons traiter les éléments en fonction de la priorité.
Ce que vous apprendrez:
- Opérations de base
- Illustration
- Implémentation des files d'attente prioritaires en C ++
- Application
- Conclusion
- lecture recommandée
Opérations de base
Laissez-nous discuter de certaines des opérations de base prises en charge par la file d'attente prioritaire.
- Insérer (élément, priorité): Insère un élément dans la file d'attente prioritaire avec une priorité donnée.
- getHighestPriority (): Renvoie un élément avec la priorité la plus élevée.
- deleteHighestPriority (): Supprime un élément avec la priorité la plus élevée.
En dehors des opérations ci-dessus, nous pouvons également utiliser les opérations de file d'attente normales comme isEmpty (), isFull () et peek ().
Illustration
Voyons une illustration de la file d'attente prioritaire. Pour des raisons de simplicité, nous utiliserons des caractères ASCII comme éléments dans la file d'attente prioritaire. Plus la valeur ASCII est élevée, plus la priorité est élevée.
État initial - File d'attente prioritaire (PQ) - {} => vide
De l'illustration ci-dessus, nous voyons que l'opération d'insertion est similaire à une file d'attente ordinaire. Mais lorsque nous appelons «deleteHighestPriority» pour la file d'attente prioritaire, l'élément avec la priorité la plus élevée est supprimé en premier.
Par conséquent, la première fois que nous appelons cette fonction, l'élément O est supprimé tandis que la deuxième fois, l'élément M est supprimé car il a une priorité plus élevée que G et A.
Implémentation des files d'attente prioritaires en C ++
Les files d'attente prioritaires peuvent être implémentées en utilisant:
# 1) Tableaux / listes liées
Nous pouvons implémenter les files d'attente prioritaires à l'aide de tableaux et c'est l'implémentation la plus simple pour les files d'attente prioritaires.
Pour représenter les éléments de la file d'attente prioritaire, nous pouvons simplement déclarer une structure comme ci-dessous:
struct pq_item{ int item; int priority; };Nous avons également déclaré la priorité pour chaque article.
Pour insérer un nouvel élément dans la file d'attente prioritaire, nous devons simplement insérer l'élément à la fin du tableau.
Pour obtenir l'élément de la file d'attente à l'aide de getHighestPriority (), nous devons parcourir le tableau depuis le début et renvoyer l'élément avec la priorité la plus élevée.
De même, pour supprimer l'élément de la file d'attente à l'aide de l'opération deleteHighestPriority, nous devons parcourir l'ensemble du tableau et supprimer l'élément avec la priorité la plus élevée. Ensuite, déplacez tous les autres éléments après l'élément supprimé, d'une position en arrière.
Nous pouvons également implémenter la file d'attente prioritaire à l'aide d'une liste chaînée. Nous pouvons effectuer toutes les opérations de la même manière que les tableaux. La seule différence est que nous n'avons pas besoin de déplacer les éléments après avoir appelé deleteHighestPriority.
# 2) Des tas
L'utilisation de tas pour implémenter une file d'attente prioritaire est le moyen le plus efficace et offre de bien meilleures performances par rapport aux listes et aux tableaux liés. Contrairement à la liste liée et au tableau, l'implémentation du tas prend un temps O (logn) pour les opérations d'insertion et de suppression de la file d'attente prioritaire. Get operation, getHighestPriority prend un temps O (1).
# 3) File d'attente de priorité intégrée dans la bibliothèque de modèles standard (STL) en C ++
En C ++, nous avons une file d'attente prioritaire en tant que classe adaptative de conteneur, conçue de telle manière que l'élément le plus élevé est le premier élément de la file d'attente et que tous les éléments sont dans l'ordre décroissant.
Ainsi, chaque élément de la file d'attente prioritaire a une priorité fixe.
Nous avons la classe en STL, qui contient l'implémentation de la file d'attente prioritaire.
Les différentes opérations prises en charge par la file d'attente prioritaire sont les suivantes:
- priority_queue :: size (): Renvoie la taille de la file d'attente.
- priority_queue :: empty (): Vérifie si la file d'attente est vide et renvoie son état.
- priority_queue :: top (): Renvoie une référence à l'élément le plus haut de la file d'attente prioritaire.
- priority_queue :: push (): Ajoute un élément à la fin de la file d'attente prioritaire.
- priority_queue :: pop (): Supprime le premier élément de la file d'attente prioritaire.
- priority_queue :: swap (): Utilisé pour échanger le contenu d'une file d'attente prioritaire avec une autre du même type et de la même taille.
- type de valeur de file d'attente prioritaire: Le type de valeur donne le type de l'élément stocké dans une file d'attente prioritaire. Cela sert également de synonyme pour le paramètre de modèle.
- priority_queue :: emplace (): Utilisé pour insérer un nouvel élément dans le conteneur de file d'attente prioritaire en haut de la file d'attente.
Dans le programme suivant, nous verrons la fonctionnalité de la file d'attente prioritaire en STL en C ++.
#include #include using namespace std; void displaypq(priority_queue pq) { priority_queue pqueue = pq; while (!pqueue.empty()) { cout << ' ' << pqueue.top(); pqueue.pop(); } cout << '
'; } int main () { priority_queue pq; pq.push(1); pq.push(3); pq.push(5); pq.push(7); pq.push(9); cout << 'Size of the queue(pq.size()): ' << pq.size(); cout << '
Top element of the queue(pq.top()): ' << pq.top(); cout << '
The priority queue pq is : '; displaypq(pq); cout << '
Priority queue, after pq.pop() operation : '; pq.pop(); displaypq(pq); return 0; } Production:
quelle est la clé de sécurité sur le routeur
Taille de la file d'attente (pq.size ()): 5
Élément supérieur de la file d'attente (pq.top ()): 9
La file d'attente prioritaire pq est: 9 7 5 3 1
File d'attente prioritaire, après l'opération pq.pop (): 7 5 3 1
Implémentation Java pour la file d'attente prioritaire
La file d'attente prioritaire en java est une file d'attente spéciale dans laquelle tous les éléments de la file d'attente sont classés selon un ordre naturel ou un ordre personnalisé à l'aide d'un comparateur fourni avec la file d'attente.
Une file d'attente prioritaire en Java ressemble à l'illustration ci-dessous:
Dans la file d'attente de priorité Java, les éléments sont disposés de telle sorte que le plus petit élément se trouve à l'avant de la file d'attente et le plus grand élément à l'arrière de la file d'attente. Ainsi, lorsque nous supprimons l'élément de la file d'attente prioritaire, c'est toujours le plus petit élément qui est supprimé.
La classe qui implémente la file d'attente prioritaire en Java est «PriorityQueue» et fait partie du cadre des collections de Java. Il implémente l'interface «Queue» de Java.
Voici la hiérarchie des classes pour la classe Java PriorityQueue.
Vous trouverez ci-dessous un exemple de fonctionnalité de file d'attente prioritaire avec des entiers comme éléments en Java.
import java.util.*; class Main { public static void main(String args()) { // Create empty priority queue PriorityQueue priority_Queue = new PriorityQueue(); // Adding items to the priority_Queue using add() priority_Queue.add(1); priority_Queue.add(3); priority_Queue.add(5); priority_Queue.add(7); // display the most priority element System.out.println('peek()::Head value:' + priority_Queue.peek()); // Print all elements in Priotity queue System.out.println('The priority queue:'); Iterator itr = priority_Queue.iterator(); while (itr.hasNext()) System.out.print(itr.next() + ' '); // poll() function to remove the queue elements priority_Queue.poll(); System.out.println('
After poll() function, priority queue:'); Iterator itr2 = priority_Queue.iterator(); while (itr2.hasNext()) System.out.print(itr2.next() + ' '); // remove() function with priority queue priority_Queue.remove(5); System.out.println('
After Remove(5) function, priority queue:'); Iterator itr3 = priority_Queue.iterator(); while (itr3.hasNext()) System.out.print(itr3.next() + ' '); // Check if an element is present using contains() boolean b = priority_Queue.contains(3); System.out.println ( '
Priority queue contains 3?: ' + b); // use toArray() function to get objects from the queue and display the array elements Object() arr = priority_Queue.toArray(); System.out.println ( 'Array elements: '); for (int i = 0; i Production:
peek () :: Valeur de la tête: 1
La file d'attente prioritaire:
1 3 5 7
Après la fonction poll (), file d'attente prioritaire:
3 7 5
Après la fonction Remove (5), file d'attente prioritaire:
3 7
La file d'attente prioritaire contient 3?: Vrai
Éléments du tableau:
Valeur: 3
Valeur: 7
Dans le programme ci-dessus, nous utilisons la classe PriorityQueue de Java pour créer un objet PriorityQueue qui contient un objet Integer. Nous ajoutons des éléments dans la file d'attente à l'aide de la fonction «ajouter». Ensuite, la fonction poll () est appelée et elle supprime l'élément du début de la file d'attente qui se trouve être le moindre élément.
Encore une fois, nous appelons la fonction «remove ()» qui supprime l'élément spécifié comme paramètre de la file d'attente. Nous utilisons également la fonction «Contains ()» pour vérifier si un élément particulier est présent dans la file d'attente. Enfin, nous convertissons la file d'attente en un objet tableau en utilisant la fonction «toArray ()».
Application
- Équilibrage de charge du système d'exploitation et gestionnaires d'interruption: Les fonctions du système d'exploitation telles que l'équilibrage de charge et la gestion des interruptions sont implémentées à l'aide de files d'attente prioritaires. L'activité d'équilibrage de charge planifie les ressources avec la priorité la plus élevée afin de mener efficacement notre équilibrage de charge. La gestion des interruptions est effectuée en traitant les interruptions avec la priorité la plus élevée. Cette fonctionnalité peut être mise en œuvre efficacement en utilisant les files d'attente prioritaires.
- Routage: Le routage est une fonction utilisée pour acheminer les ressources du réseau afin d'obtenir un débit maximal avec un temps de rotation minimum. Cela peut également être mis en œuvre à l'aide de la file d'attente prioritaire.
- Urgence hospitalière: Dans une salle d'urgence d'un hôpital, les patients sont pris en charge en fonction de la gravité de l'état du patient. Cela peut être simulé à l'aide de files d'attente prioritaires.
- Algorithme de chemin le plus court de Dijkstra: Ici, le graphique est stocké sous forme de liste de contiguïté et nous pouvons utiliser une file d'attente prioritaire pour extraire efficacement l'arête pondérée minimale de la liste de contiguïté pour implémenter l'algorithme de chemin le plus court de Dijkstra.
- La file d'attente prioritaire peut également être utilisée pour stocker les clés de nœud et extraire le nœud de clé minimum lors de l'implémentation de Spanning Tree.
Conclusion
Les files d'attente prioritaires ne sont rien d'autre que l'extension de la file d'attente. Mais contrairement aux files d'attente qui ajoutent / suppriment des éléments en utilisant l'approche FIFO, dans la file d'attente prioritaire, les éléments sont supprimés de la file d'attente en fonction de la priorité. Ainsi, chaque élément de la file d'attente est associé à une priorité et l'élément avec la priorité la plus élevée est le premier à être retiré de la file d'attente.
La file d'attente prioritaire a trois opérations principales, à savoir insert (), getHighestPriority () et deleteHighestPriority (). La file d'attente prioritaire peut être implémentée à l'aide de tableaux ou de listes chaînées mais le fonctionnement n'est pas très efficace. La file d'attente prioritaire peut également être implémentée à l'aide de tas et les performances sont beaucoup plus rapides.
En C ++, nous avons également une classe de conteneur qui implémente la fonctionnalité d'une file d'attente prioritaire. En Java, il existe une classe intégrée priority_queue qui fournit les fonctionnalités d'une file d'attente prioritaire.
La file d'attente prioritaire est principalement utilisée dans les applications qui nécessitent le traitement des éléments en fonction de la priorité. Par exemple, il est utilisé dans la gestion des interruptions.
Notre prochain didacticiel explorera tout sur la file d'attente circulaire, qui est encore une autre extension de la file d'attente.
=> Visitez ici pour le cours C ++ complet d'experts.
lecture recommandée
- Structure de données de file d'attente en C ++ avec illustration
- File d'attente prioritaire dans STL
- Empiler la structure de données en C ++ avec illustration
- Structure de données de liste liée circulaire en C ++ avec illustration
- Structure de données de liste liée en C ++ avec illustration
- Structure de données de liste doublement liée en C ++ avec illustration
- Introduction aux structures de données en C ++
- Comment tester la file d'attente de messagerie d'application: didacticiel IBM WebSphere MQ Intro