Une file de priorité est une structure de données qui associe une priorité à chaque élément. Elle permet d'insérer des éléments selon leur priorité et de les extraire dans l'ordre de priorité décroissante (ou croissante).

1. Représentation d'une file de priorité en Python

En Python, vous pouvez utiliser le module queue pour implémenter une file de priorité. Plus précisément, vous pouvez utiliser la classe PriorityQueue du module queue.

Voici un exemple de code Python pour créer une file de priorité, insérer des éléments et les extraire selon leur priorité :

from queue import PriorityQueue

# Création d'une file de priorité
file_priorite = PriorityQueue()

# Insertion d'éléments avec leur priorité
file_priorite.put((3, "Élément 1"))  # (priorité, élément)
file_priorite.put((1, "Élément 2"))
file_priorite.put((2, "Élément 3"))

# Extraction des éléments dans l'ordre de priorité décroissante
while not file_priorite.empty():
    priorite, element = file_priorite.get()
    print(element)  # Affiche : Élément 2, Élément 3, Élément 1

Dans cet exemple, nous utilisons un tuple (priorité, élément) pour représenter chaque élément de la file de priorité. Les éléments sont insérés dans la file en utilisant la méthode put(), et ils sont extraits dans l'ordre de priorité décroissante en utilisant la méthode get().

2. Utilisation des files de priorité

Les files de priorité sont couramment utilisées dans de nombreux domaines, tels que les algorithmes de recherche, le traitement des tâches avec des priorités, la planification des événements, etc.

Par exemple, voici un exemple de code Python qui utilise une file de priorité pour trier une liste d'éléments selon leur valeur :

from queue import PriorityQueue

def tri_par_priorite(liste):
    file_priorite = PriorityQueue()
    
    for element in liste:
        file_priorite.put((element, element))
    
    liste_triee = []
    while not file_priorite.empty():
        priorite, element = file_priorite.get()
        liste_triee.append(element)
    
    return liste_triee

ma_liste = [5, 2, 7, 1, 3]
liste_triee = tri_par_priorite(ma_liste)
print(liste_triee)  # Affiche : [1, 2, 3, 5, 7]

Dans cet exemple, nous utilisons une file de priorité pour trier les éléments de la liste ma_liste. Chaque élément est inséré dans la file avec sa propre valeur comme priorité, puis les éléments sont extraits dans l'ordre croissant de priorité pour obtenir la liste triée.

3. Conclusion

Les files de priorité sont des structures de données très utiles pour gérer des éléments avec des priorités. Elles permettent d'insérer des éléments selon leur priorité et de les extraire dans l'ordre de priorité souhaité.

Tas Binaires

Un tas binaire est une structure de données arborescente qui satisfait la propriété suivante : pour chaque nœud i autre que la racine, la valeur stockée dans le nœud père est plus petite (ou plus grande) que les valeurs stockées dans ses nœuds fils. Cette propriété est appelée propriété du tas.

1. Représentation d'un tas binaire en Python

En Python, un tas binaire peut être représenté à l'aide d'une liste. Les indices de la liste correspondent aux positions des nœuds dans le tas binaire. Les relations entre les nœuds père et les nœuds fils peuvent être déduites en utilisant des formules mathématiques simples.

Voici un exemple de code Python pour créer un tas binaire, insérer des éléments et extraire l'élément de plus haute priorité :

import heapq

# Création d'un tas binaire vide
tas = []

# Insertion d'éléments
heapq.heappush(tas, 3)
heapq.heappush(tas, 1)
heapq.heappush(tas, 2)

# Extraction de l'élément de plus haute priorité
element = heapq.heappop(tas)
print(element)  # Affiche : 1

Dans cet exemple, nous utilisons le module heapq de Python pour créer et manipuler un tas binaire. La fonction heappush() est utilisée pour insérer des éléments dans le tas, tandis que la fonction heappop() est utilisée pour extraire l'élément de plus haute priorité (le plus petit élément dans ce cas).

2. Utilisation des tas binaires

Les tas binaires sont couramment utilisés pour implémenter des structures de données et des algorithmes efficaces, tels que les files de priorité, le tri par tas, l'algorithme de Dijkstra, etc.

Par exemple, voici un exemple de code Python qui utilise un tas binaire pour trier une liste d'éléments :

import heapq

def tri_par_tas(liste):
    tas = []
    for element in liste:
        heapq.heappush(tas, element)
    
    liste_triee = []
    while tas:
        element = heapq.heappop(tas)
        liste_triee.append(element)
    
    return liste_triee

ma_liste = [5, 2, 7, 1, 3]
liste_triee = tri_par_tas(ma_liste)
print(liste_triee)  # Affiche : [1, 2, 3, 5, 7]

Dans cet exemple, nous utilisons un tas binaire pour trier les éléments de la liste ma_liste. Chaque élément est inséré dans le tas à l'aide de la fonction heappush(), puis les éléments sont extraits dans l'ordre croissant de priorité à l'aide de la fonction heappop() pour obtenir la liste triée.

3. Conclusion

Les tas binaires sont des structures de données efficaces pour maintenir et manipuler des éléments selon leur priorité. Ils permettent d'insérer des éléments et d'extraire l'élément de plus haute (ou plus basse) priorité de manière efficace.

Exercices - corrigés: les files de priorité

Exercice 1: ★ ★ ☆ ☆ ☆

Écrivez une classe Python qui implémente une pile (stack) utilisant une liste comme structure de données sous-jacente. La pile doit prendre en charge les opérations suivantes :

• enfiler(element): ajoute un élément à la file de priorité avec sa priorité.
  
• defiler(): retire et renvoie l'élément ayant la plus haute priorité dans la file de priorité.
• est_vide(): renvoie True si la file de priorité est vide, False sinon.

class FileDePriorite:
    def __init__(self):
        self.elements = []

    def enfiler(self, element, priorite):
        self.elements.append((element, priorite))

    def defiler(self):
        if self.est_vide():
            raise IndexError("La file de priorité est vide.")
        indice_prioritaire = 0
        priorite_max = self.elements[0][1]
        for i, (_, priorite) in enumerate(self.elements[1:], start=1):
            if priorite > priorite_max:
                priorite_max = priorite
                indice_prioritaire = i
        return self.elements.pop(indice_prioritaire)[0]

    def est_vide(self):
        return len(self.elements) == 0

# Exemple d'utilisation
file_de_priorite = FileDePriorite()
file_de_priorite.enfiler('A', 3)
file_de_priorite.enfiler('B', 1)
file_de_priorite.enfiler('C', 2)
print(file_de_priorite.defiler())  # Résultat : 'B'
print(file_de_priorite.defiler())  # Résultat : 'C'
print(file_de_priorite.est_vide())  # Résultat : False
print(file_de_priorite.defiler())  # Résultat : 'A'
print(file_de_priorite.est_vide())  # Résultat : True

Exercice 2: ★ ★ ☆ ☆ ☆

Écrivez une fonction Python qui prend en entrée une liste d'éléments et une liste de priorités correspondante, et qui renvoie une nouvelle liste contenant les éléments triés par ordre de priorité. Les éléments ayant la même priorité doivent être conservés dans leur ordre d'apparition d'origine.

def tri_par_priorite(elements, priorites):
    assert len(elements) == len(priorites), "Les listes doivent avoir la même longueur."

    file_de_priorite = FileDePriorite()

    for element, priorite in zip(elements, priorites):
        file_de_priorite.enfiler(element, priorite)

    elements_tries = []
    while not file_de_priorite.est_vide():
        elements_tries.append(file_de_priorite.defiler())

    return elements_tries

# Exemple d'utilisation
elements = ['A', 'B', 'C', 'D']
priorites = [3, 1, 2, 2]
resultat = tri_par_priorite(elements, priorites)
print(resultat)  # Résultat : ['B', 'C', 'D', 'A']

Exercice 3: ★ ★ ☆ ☆ ☆

Écrivez une fonction Python qui prend en entrée une liste d'éléments et une liste de poids correspondante, et qui renvoie une nouvelle liste contenant les éléments triés par ordre croissant de poids. Les éléments ayant le même poids doivent être conservés dans leur ordre d'apparition d'origine.

def tri_par_poids(elements, poids):
    assert len(elements) == len(poids), "Les listes doivent avoir la même longueur."

    file_de_priorite = FileDePriorite()

    for element, poids in zip(elements, poids):
        file_de_priorite.enfiler(element, poids)

    elements_tries = []
    while not file_de_priorite.est_vide():
        elements_tries.append(file_de_priorite.defiler())

    return elements_tries

# Exemple d'utilisation
elements = ['A', 'B', 'C', 'D']
poids = [3, 1, 2, 2]
resultat = tri_par_poids(elements, poids)
print(resultat)  # Résultat : ['B', 'C', 'D', 'A']

Exercice 4:★ ★ ★ ☆ ☆

Supposons que vous travaillez sur un projet de gestion de files d'attente dans un parc d'attractions. Vous devez implémenter une file de priorité pour gérer les visiteurs en fonction de leur type de billet et de leur priorité. Les types de billets sont les suivants :

• Billet normal (priorité 1)
• Billet prioritaire (priorité 2)
• Billet VIP (priorité 3)

Votre tâche consiste à écrire une fonction Python qui prend en entrée une liste de visiteurs avec leurs types de billets et qui renvoie l'ordre dans lequel les visiteurs doivent entrer dans le parc d'attractions en respectant leur priorité.

class Visiteur:
    def __init__(self, nom, type_billet):
        self.nom = nom
        self.type_billet = type_billet

    def __repr__(self):
        return f"Visiteur({self.nom}, {self.type_billet})"

def gestion_files_parc_attractions(visiteurs):
    file_de_priorite = FileDePriorite()

    for visiteur in visiteurs:
        if visiteur.type_billet == "normal":
            priorite = 1
        elif visiteur.type_billet == "prioritaire":
            priorite = 2
        elif visiteur.type_billet == "VIP":
            priorite = 3
        else:
            raise ValueError(f"Type de billet invalide pour le visiteur {visiteur.nom}.")

        file_de_priorite.enfiler(visiteur, priorite)

    ordre_entree = []
    while not file_de_priorite.est_vide():
        visiteur = file_de_priorite.defiler()
        ordre_entree.append(visiteur)

    return ordre_entree

# Exemple d'utilisation
visiteurs = [
    Visiteur("Alice", "normal"),
    Visiteur("Bob", "VIP"),
    Visiteur("Charlie", "prioritaire"),
    Visiteur("Dave", "normal"),
    Visiteur("Eve", "prioritaire"),
    Visiteur("Frank", "VIP")
]
resultat = gestion_files_parc_attractions(visiteurs)
for visiteur in resultat:
    print(visiteur.nom)

# Résultat attendu :
# Bob
# Charlie
# Eve
# Frank
# Alice
# Dave

ⓘ Dans cet exercice, vous devez utiliser une file de priorité pour trier les visiteurs en fonction de leur type de billet et respecter leur priorité lors de l'entrée dans le parc d'attractions. Cela vous permettra de mettre en pratique les concepts de files de priorité dans un contexte concret.

Exercice 5: ★ ★ ★ ☆ ☆

Supposons que vous travaillez sur un système de gestion des tâches d'un projet logiciel. Chaque tâche est associée à une priorité allant de 1 (priorité la plus basse) à 5 (priorité la plus élevée). Vous devez implémenter une file de priorité pour gérer les tâches en fonction de leur priorité. Les tâches sont représentées par des objets de la classe Tache, qui a les attributs nom et priorite.

Votre tâche consiste à écrire une fonction Python qui prend en entrée une liste de tâches et qui renvoie l'ordre dans lequel les tâches doivent être traitées, en respectant leur priorité.

class Tache:
    def __init__(self, nom, priorite):
        self.nom = nom
        self.priorite = priorite

    def __repr__(self):
        return f"Tache({self.nom}, {self.priorite})"

def gestion_files_taches(taches):
    file_de_priorite = FileDePriorite()

    for tache in taches:
        priorite = tache.priorite
        file_de_priorite.enfiler(tache, priorite)

    ordre_traitement = []
    while not file_de_priorite.est_vide():
        tache = file_de_priorite.defiler()
        ordre_traitement.append(tache)

    return ordre_traitement

# Exemple d'utilisation
taches = [
    Tache("Implémenter la fonctionnalité A", 3),
    Tache("Réviser les tests unitaires", 4),
    Tache("Rédiger la documentation", 2),
    Tache("Corriger les bugs", 5),
    Tache("Optimiser les performances", 5),
    Tache("Ajouter des fonctionnalités supplémentaires", 3)
]
resultat = gestion_files_taches(taches)
for tache in resultat:
    print(tache.nom)

# Résultat attendu :
# Corriger les bugs
# Optimiser les performances
# Réviser les tests unitaires
# Implémenter la fonctionnalité A
# Ajouter des fonctionnalités supplémentaires
# Rédiger la documentation

Exercice 6: ★ ★ ☆ ☆ ☆

Écrivez une classe Python qui implémente une file (queue) utilisant une liste comme structure de données sous-jacente. La file doit prendre en charge les opérations suivantes :

• enfiler(element): ajoute un élément à la fin de la file.
• enfiler(element): ajoute un élément à la fin de la file.
• est_vide(): renvoie True si la file est vide, False sinon.
  

class File:
    def __init__(self):
        self.elements = []

    def enfiler(self, element):
        self.elements.append(element)

    def defiler(self):
        if self.est_vide():
            raise IndexError("La file est vide.")
        return self.elements.pop(0)

    def est_vide(self):
        return len(self.elements) == 0

# Exemple d'utilisation
file = File()
file.enfiler(1)
file.enfiler(2)
file.enfiler(3)
print(file.defiler())  # Résultat : 1
print(file.defiler())  # Résultat : 2
print(file.est_vide())  # Résultat : False
print(file.defiler())  # Résultat : 3
print(file.est_vide())  # Résultat : True

Exercices - corrigés: les tas binaires

Exercice 1: ★ ★ ☆ ☆ ☆

Écrivez une fonction Python qui prend en entrée un tableau d'entiers et qui retourne le plus grand élément en utilisant un tas binaire.

import heapq

def trouver_plus_grand_element(tableau):
    tas_binaire = []
    for element in tableau:
        heapq.heappush(tas_binaire, -element)
    return -heapq.heappop(tas_binaire)

# Exemple d'utilisation
tableau = [5, 8, 2, 10, 3]
plus_grand_element = trouver_plus_grand_element(tableau)
print(plus_grand_element)  # Résultat : 10

Exercice 2: ★ ★ ☆ ☆ ☆

Écrivez une fonction Python qui prend en entrée un tableau d'entiers et qui retourne les k plus grands éléments en utilisant un tas binaire.

import heapq

def trouver_k_plus_grands_elements(tableau, k):
    tas_binaire = []
    for element in tableau:
        heapq.heappush(tas_binaire, -element)
        if len(tas_binaire) > k:
            heapq.heappop(tas_binaire)
    return [-element for element in tas_binaire]

# Exemple d'utilisation
tableau = [5, 8, 2, 10, 3, 6, 4, 7, 9]
k = 3
k_plus_grands_elements = trouver_k_plus_grands_elements(tableau, k)
print(k_plus_grands_elements)  # Résultat : [8, 9, 10]

Exercice 3: ★ ★ ☆ ☆ ☆

Écrivez une fonction Python qui prend en entrée un tableau d'entiers et qui retourne les éléments triés dans l'ordre croissant en utilisant un tas binaire.

import heapq

def trier_tableau(tableau):
    tas_binaire = []
    for element in tableau:
        heapq.heappush(tas_binaire, element)
    elements_tries = []
    while tas_binaire:
        element = heapq.heappop(tas_binaire)
        elements_tries.append(element)
    return elements_tries

# Exemple d'utilisation
tableau = [5, 8, 2, 10, 3]
tableau_trie = trier_tableau(tableau)
print(tableau_trie)  # Résultat : [2, 3, 5, 8, 10]

Exercice 4: ★ ★ ★ ☆ ☆

Supposons que vous travaillez sur un projet de gestion des tâches dans une entreprise. Chaque tâche est représentée par un objet de la classe Tache, qui a les attributs nom et priorite. Vous devez implémenter une fonction qui utilise un tas binaire pour trier les tâches en fonction de leur priorité.

import heapq

class Tache:
    def __init__(self, nom, priorite):
        self.nom = nom
        self.priorite = priorite

    def __repr__(self):
        return f"Tache({self.nom}, {self.priorite})"

def trier_taches(taches):
    tas_binaire = []
    for tache in taches:
        heapq.heappush(tas_binaire, (tache.priorite, tache))
    taches_triees = []
    while tas_binaire:
        priorite, tache = heapq.heappop(tas_binaire)
        taches_triees.append(tache)
    return taches_triees

# Exemple d'utilisation
taches = [
    Tache("Implémenter la fonctionnalité A", 3),
    Tache("Réviser les tests unitaires", 4),
    Tache("Rédiger la documentation", 2),
    Tache("Corriger les bugs", 5),
    Tache("Optimiser les performances", 5),
    Tache("Ajouter des fonctionnalités supplémentaires", 3)
]
taches_triees = trier_taches(taches)
for tache in taches_triees:
    print(tache.nom)

# Résultat attendu :
# Rédiger la documentation
# Implémenter la fonctionnalité A
# Ajouter des fonctionnalités supplémentaires
# Réviser les tests unitaires
# Corriger les bugs
# Optimiser les performances

ⓘ Dans cet exercice, vous devez utiliser un tas binaire pour trier les tâches en fonction de leur priorité. Cela vous permettra de les ordonner de manière efficace pour la gestion des tâches dans votre projet.

Exercice 5: ★ ★ ★ ☆ ☆

Supposons que vous développez un système de gestion des événements pour une application. Chaque événement est représenté par un objet de la classe Evenement, qui a les attributs nom et heure. Vous devez implémenter une fonction qui utilise un tas binaire pour trouver l'événement le plus proche dans le temps.

import heapq

class Evenement:
    def __init__(self, nom, heure):
        self.nom = nom
        self.heure = heure

    def __repr__(self):
        return f"Evenement({self.nom}, {self.heure})"

def trouver_evenement_proche(evenements, heure_actuelle):
    tas_binaire = []
    for evenement in evenements:
        heapq.heappush(tas_binaire, (abs(evenement.heure - heure_actuelle), evenement))
    evenement_proche = heapq.heappop(tas_binaire)[1]
    return evenement_proche

# Exemple d'utilisation
evenements = [
    Evenement("Réunion d'équipe", 9),
    Evenement("Déjeuner", 12),
    Evenement("Présentation client", 15),
    Evenement("Séance de brainstorming", 14),
    Evenement("Formation interne", 11)
]
heure_actuelle = 10
evenement_proche = trouver_evenement_proche(evenements, heure_actuelle)
print(evenement_proche.nom)

# Résultat attendu : Formation interne

ⓘ Dans cet exercice, vous devez utiliser un tas binaire pour trouver l'événement le plus proche dans le temps par rapport à une heure donnée. Cela vous permettra de proposer à l'utilisateur l'événement à venir le plus proche et de planifier en conséquence.