🎯 Files de Priorité (Priority Queue) : Concepts et Applications

Imaginez une situation où certaines tâches sont plus urgentes que d'autres. Les files de priorité permettent de gérer ces scénarios en traitant les éléments en fonction de leur priorité plutôt que de leur ordre d'arrivée.

📚 Qu'est-ce qu'une File de Priorité ?

Une file de priorité est une structure de données où chaque élément a une priorité associée. Les éléments sont retirés en fonction de leur priorité, les éléments avec la priorité la plus élevée étant servis en premier.

Il existe deux types de files de priorité :

Min PQ : La priorité la plus basse est servie en premier.
Max PQ : La priorité la plus élevée est servie en premier.

🌲 Qu'est-ce qu'un Heap ?

Un heap est une structure de données en forme d'arbre binaire utilisée pour implémenter les files de priorité. Il existe deux types de heaps :

Min-heap : Chaque nœud est inférieur ou égal à ses enfants.
Max-heap : Chaque nœud est supérieur ou égal à ses enfants.

🔍 Comment Choisir entre un Min-Heap et un Max-Heap ?

Le choix dépend de la manière dont vous voulez traiter les éléments prioritaires :

Min-Heap :

Utilisé pour accéder rapidement à l'élément de plus basse priorité.
Cas d'utilisation :

🛣️ Algorithmes de plus court chemin (comme Dijkstra).
🗓️ Planification de tâches avec des coûts.
⏱️ Traitement d'événements dans des simulations.

Max-Heap :

Utilisé pour accéder rapidement à l'élément de plus haute priorité.
Cas d'utilisation :

🏆 Classements ou scores pour obtenir les valeurs les plus élevées en premier.
🚨 Systèmes de priorisation en temps réel.
🏥 File d'attente d'urgence dans les hôpitaux.

Si nécessaire, vous pouvez transformer un min-heap en max-heap en inversant les priorités (par exemple, en multipliant par -1).

🛠️ Quand et Où Utilise-t-on une File de Priorité ?

🖥️ Planification des tâches dans les systèmes d'exploitation.
🌐 Algorithmes de graphes comme Dijkstra.
📅 Traitement d'événements dans des simulations.

📊 Analyse de Complexité

Opération	Complexité
Insertion	O(log n)
Extraction (min/max)	O(log n)
Accès au min/max	O(1)

💻 Implémentation en Python

Voici comment implémenter une file de priorité en utilisant un min-heap avec le module heapq de Python :

import heapq

class PriorityQueue:
    def __init__(self):
        self.heap = []

    # Ajouter un élément dans la file de priorité
    def enqueue(self, priority, item):
        heapq.heappush(self.heap, (priority, item))
        print(f"Élément {item} avec priorité {priority} ajouté")

    # Retirer l'élément avec la priorité la plus basse (min-heap)
    def dequeue(self):
        if not self.is_empty():
            priority, item = heapq.heappop(self.heap)
            print(f"Élément {item} avec priorité {priority} retiré")
            return item
        else:
            print("La file de priorité est vide")
            return None

    # Consulter l'élément avec la priorité la plus basse sans le retirer
    def peek(self):
        if not self.is_empty():
            priority, item = self.heap[0]
            return item
        else:
            print("La file de priorité est vide")
            return None

    # Vérifier si la file de priorité est vide
    def is_empty(self):
        return len(self.heap) == 0

    # Afficher la file de priorité
    def display(self):
        print("État actuel de la file de priorité :", self.heap)

# Utilisation de la file de priorité
pq = PriorityQueue()
pq.enqueue(2, "Tâche moyenne")
pq.enqueue(1, "Tâche haute priorité")
pq.enqueue(3, "Tâche basse priorité")
pq.display()                  # Affiche l'état actuel du heap
print("Élément prioritaire :", pq.peek())  # Affiche la tâche de plus haute priorité
pq.dequeue()                  # Retire l'élément de plus haute priorité
pq.display()                  # Affiche l'état actuel après retrait

Explication du Code :

enqueue : Ajoute un élément avec une priorité donnée.
dequeue : Retire l'élément avec la priorité la plus basse.
peek : Consulte l'élément avec la priorité la plus basse sans le retirer.
is_empty : Vérifie si la file de priorité est vide.
display : Affiche l'état actuel du heap.

💪 Exercices

Testez vos connaissances avec ces exercices :

# Exercices :

# 1. Implémentez une file de priorité en utilisant un max-heap pour extraire l'élément avec la priorité la plus élevée en premier.

# 2. Écrivez un programme qui simule la planification des processus dans un système d'exploitation en utilisant une file de priorité.

# 3. Implémentez l'algorithme de Dijkstra pour trouver le chemin le plus court dans un graphe en utilisant une file de priorité.

# 4. Créez une file de priorité qui permet de changer la priorité d'un élément déjà présent.

# 5. Écrivez un programme pour fusionner plusieurs files de priorité en une seule.

🎉 Conclusion

Les files de priorité sont des structures de données puissantes pour gérer des éléments en fonction de leur priorité. Elles sont essentielles dans de nombreux algorithmes et applications où le traitement prioritaire est crucial.

Leçons