File d'attente prioritaire dans la structure de données : tout ce que vous devez savoir
Publié: 2021-04-07Table des matières
introduction
Les files d'attente prioritaires dans les structures de données sont une forme importante d'ADT (types de données abstraits). Chaque élément se voit attribuer une priorité, qui sert de caractéristique pour les définir et les agencer.
L'ADTS fait partie du domaine de la science des données, dans lequel les structures de données sont utilisées comme modèles d'arrangement pour stocker des informations et gérer des opérations telles que l'accès, l'ajout, la recherche et la modification de valeurs de données. Les méthodologies utilisées pour cet agencement des données orientent leur organisation. Les structures de données déterminent également la direction du flux de données et les relations partagées au sein des éléments du système.
Les experts ont estimé que d'ici 2025, le total des données mondiales pourrait dépasser 175 zettaoctets. Pour gérer de telles quantités de données, des structures de données sont utilisées pour gérer efficacement de grandes bases de données et à des fins d'indexation. Différents types de structures de données telles que des piles, des files d'attente, des tableaux, des tas, etc., sont utilisés lors des étapes de programmation. Les piles et les files d'attente sont une forme linéaire de structures de données, car les données sont stockées séquentiellement, les unes après les autres. Ils n'ont pas de branches et chaque valeur d'élément/donnée doit être disposée en ligne droite.
Disposition des piles et des files d'attente
Une pile suit une approche LIFO (Last In First Out) pour la disposition du stockage, tandis qu'une file d'attente suit une disposition FIFO (First In First Out). C'est un facteur important pour différencier ces deux structures de données linéaires. Leurs applications sont décidées en fonction de leur approche LIFO/FIFO, car elles dépendent de leur utilisation informatique unique.
Pour en savoir plus sur la science des données et des exemples de structures de données, inscrivez-vous au diplôme PG en Big Data, hébergé par upGrad.com .
Pour une file d'attente, FIFO établit que lorsque plusieurs éléments sont ajoutés au système, le premier élément ajouté serait le premier à être consulté/supprimé.
5 opérations de base pouvant être effectuées sur une file d'attente
1. Mettre en file d'attente : Cette opération est effectuée lorsque nous voulons ajouter un élément à la file d'attente.
2. Dequeue : Cet opérateur est utilisé pour supprimer un élément de la file d'attente.
3. IsEmpty : cette opération est utilisée pour vérifier si la file d'attente est vide et si aucun retrait supplémentaire n'est possible.
4. IsFull : cet opérateur vérifie si la file d'attente est pleine et ne peut pas gérer d'autres ajouts à la file d'attente.
5. Peek : l'opérateur Peek rappelle/affiche simplement la valeur/l'élément de données attendu de la file d'attente sans le supprimer de sa séquence allouée.
Découvrez pourquoi la science des données est importante et ajoute de la valeur à l'entreprise grâce à ce blog informatif de upGrad.com.
File d'attente prioritaire dans la structure de données
Les files d'attente prioritaires ont une priorité supplémentaire associée à chacun de leurs éléments. Ils ne suivent pas les approches FIFO comme les files d'attente traditionnelles. Au lieu de cela, une file d'attente prioritaire dans la structure de données est organisée de manière à ce que les éléments "de haute priorité" soient servis avant leurs homologues "de faible priorité".
La valeur de l'élément est souvent prise en considération lors de l'attribution de la valeur prioritaire à celui-ci. La file d'attente prioritaire diffère d'une file d'attente traditionnelle en ce sens que l'élément le plus prioritaire serait récupéré en premier lorsque nous essayons de supprimer l'élément suivant de la file d'attente.
Une autre condition préalable des files d'attente prioritaires est que les données entrées dans ces files d'attente doivent être ordonnées de manière séquentielle. Cela signifie que les éléments de données individuels doivent être comparables les uns aux autres de manière à ce que leur disposition puisse être séquencée du plus bas au plus grand ou du plus grand au plus bas. Cela est nécessaire pour allouer les éléments de la file d'attente avec les priorités relatives, basées sur la comparaison les uns avec les autres.
Les applications de la file d'attente prioritaire dans la structure de données impliquent généralement leur combinaison avec d'autres structures de données non ordonnées telles que des tas, des tableaux, des listes chaînées ou des BST. Les tas fournissent la forme de combinaison la plus efficace en raison de la possibilité d'implémenter efficacement des files d'attente prioritaires.
Pour en savoir plus sur le domaine émergent de la science des données et ses applications dans l'industrie manufacturière, consultez ce blog détaillé par upGrad.com.
Opérations prises en charge dans une file d'attente prioritaire
Les opérations dans une file d'attente prioritaire permettent de traiter les informations saisies, supprimées, visualisées et modifiées. Ces opérations sont également utiles pour traverser entre les éléments de la file d'attente. Ils sont les suivants :
1. Is_empty : l'opération is_empty vérifie si la file d'attente contient un élément pour le moment.
2. Insert_with_priority : cette opération ajoute un élément à la file d'attente, ainsi que la valeur de priorité qui doit lui être associée.
3. Pull_highest_priority_element : cette opération supprime l'élément de priorité la plus élevée de la file d'attente tout en renvoyant la valeur de cet élément.
4. Peek : L'opération Peek est utilisée pour « find-max » ou « find-min », selon les résultats attendus. Cette opération ne supprime pas l'élément max/min et ne fait que le renvoyer.
L'avantage d'utiliser des tas pour la file d'attente prioritaire dans la structure de données
Les performances O(log n) sont observées pour les insertions et les suppressions lorsque les files d'attente prioritaires sont basées sur un tas. Cela améliore les performances et la fonction O(n) est construite à partir d'un ensemble "n" d'éléments. L'appariement des tas et des tas de Fibonacci fournit de meilleures limites pour les opérations de file d'attente prioritaire.
Pour en savoir plus sur la file d'attente prioritaire dans la structure des données et sur de nombreux autres concepts importants liés au domaine de la programmation, inscrivez-vous à un cours en ligne sur upGrad .
File d'attente prioritaire et éléments de tri
En tenant compte de la complexité de calcul, les files d'attente prioritaires correspondent aux algorithmes de tri en raison de leur propriété inhérente. Par exemple, nous devons collecter tous les éléments qui nécessitent un tri, puis nous devons les insérer dans une file d'attente prioritaire.
Ensuite, si nous supprimons les éléments de manière séquentielle, le résultat serait un ordre trié d'éléments. Heapsort, Smoothsort, Selection Sort, Insertion Sort et Tree sort sont les noms de certains des algorithmes de tri qui partagent une corrélation équivalente avec la file d'attente prioritaire dans les structures de données.
Applications des files d'attente prioritaires
Les files d'attente prioritaires dans la structure de données sont généralement implémentées en combinaison avec des structures de données Heap. Ils sont utilisés dans les simulations pour le séquençage, le tri et le suivi des itinéraires inexplorés. Les deux types de files d'attente prioritaires : croissant et décroissant, ont leur propre ensemble d'utilisations. Certaines de ces applications sont :
- Gestion de la bande passante
- Simulation d'événements discrets
- Algorithme de Dijkstra
- Codage de Huffman
- Meilleur algorithme de recherche en premier
- Algorithme de triangulation ROAM
- Algorithme de Prim pour un arbre couvrant minimum
Conclusion
À ce jour, environ 5 milliards de consommateurs sont directement et indirectement connectés aux données. D'ici 2025, plus de 6 milliards de personnes seraient connectées au big data. IDC prévoit une multiplication par 10 des données et prévoit une forte demande de data scientists. La file d'attente prioritaire dans la structure de données est un concept important pour les programmeurs et les scientifiques des données en raison de leur étroite corrélation et de leur application avec les structures de données en tas.
Si vous êtes curieux d'en savoir plus sur la science des données, consultez le diplôme PG de IIIT-B & upGrad en science des données qui est créé pour les professionnels en activité et propose plus de 10 études de cas et projets, des ateliers pratiques, un mentorat avec des experts de l'industrie, 1- on-1 avec des mentors de l'industrie, plus de 400 heures d'apprentissage et d'aide à l'emploi avec les meilleures entreprises.
L'inscription à un cours international en ligne de maîtrise en informatique de l'Université John Moores de Liverpool , ou à un cours PGD en cours de développement de logiciels Full Stack , DevOps, etc., peut améliorer vos perspectives d'emploi en tant que programmeur.
Apprenez des cours de science des données en ligne dans les meilleures universités du monde. Gagnez des programmes Executive PG, des programmes de certificat avancés ou des programmes de maîtrise pour accélérer votre carrière.
La file d'attente prioritaire est appliquée dans de nombreux algorithmes ainsi que dans plusieurs applications réelles. Certains d'entre eux sont décrits ci-dessous: La pile et la file d'attente sont toutes deux des structures de données linéaires. Ce qui suit illustre les principales différences entre ces deux structures de données. Pour implémenter une file d'attente prioritaire à l'aide d'un tableau, une structure est créée pour stocker les valeurs et la priorité de l'élément, puis le tableau de cette structure est créé pour stocker les éléments. Les opérations suivantes sont impliquées dans cette implémentation :Décrivez les applications de la file d'attente prioritaire ?
1. Algorithme de Huffman : L'arbre de Huffman généré dans l'algorithme de compression de données de Huffman utilise une file d'attente prioritaire pour implémenter l'arbre.
2. Algorithme de Prim : Cet algorithme utilise une file d'attente prioritaire pour accélérer le processus de la fonction minimale exacte.
3. Algorithme de Dijkstra : cet algorithme utilise un tas ou une file d'attente prioritaire pour extraire la valeur minimale. La file d'attente prioritaire rend le processus d'obtention du minimum assez efficace.
4. Système d'exploitation : La file d'attente prioritaire est utilisée dans plusieurs processus de systèmes d'exploitation tels que l'équilibrage de charge et la gestion des interruptions. Différencier pile et file d'attente ?
Pile - Les éléments fonctionnent selon le principe LIFO, c'est-à-dire que l'élément inséré en premier est l'élément supprimé en dernier. Les éléments peuvent être insérés ou supprimés à partir d'une seule extrémité appelée top. L'opération d'insertion est également connue sous le nom d'opération de poussée.
File d' attente - Les éléments sont exploités selon le principe FIFO, c'est-à-dire que l'élément inséré en premier est l'élément supprimé en premier. L'opération d'insertion est également appelée opération de mise en file d'attente. Comment une file d'attente prioritaire peut-elle être implémentée à l'aide d'un tableau ?
enqueue() - Également connue sous le nom de processus d'insertion, cette fonction est utilisée pour insérer les éléments dans la file d'attente.
peek() - Cette fonction parcourra le tableau pour renvoyer l'élément avec la priorité la plus élevée. S'il trouve deux éléments ayant la même priorité, il renvoie l'élément de valeur la plus élevée parmi eux.
dequeue() - La fonction dequeue() est utilisée pour décaler tous les éléments, 1 position vers la gauche de l'élément renvoyé par la fonction peek(), et diminue la taille de la file d'attente.