File de priorite

Une file de priorite, c'est comme les urgences a l'hopital. Les patients ne sont pas traites dans l'ordre d'arrivee, mais par ordre de gravite. Un patient avec priorite 1 (critique) passe avant un patient avec priorite 3 (leger).

Le principe : chaque élément a une priorite (un nombre). Plus le nombre est petit, plus la priorite est haute. Quand on retire un élément, on retire celui avec la plus haute priorite (le plus petit nombre).

Il y a plusieurs facons d'implémenter une file de priorite. La plus simple : une liste qu'on garde triee. A chaque ajout, on trie la liste. A chaque retrait, on prend le premier élément.

Implemente une classe FilePriorite avec :
- ajouter(priorite, tache) : ajoute la tache avec sa priorite
- retirer() : retire et retourne la tache avec la plus haute priorite (plus petit nombre). Leve IndexError si vide.
- est_vide() : retourne True si la file est vide

Exemple :
f = FilePriorite()
f.ajouter(3, 'basse')
f.ajouter(1, 'haute')
f.ajouter(2, 'moyenne')
f.retirer() renvoie 'haute'
f.retirer() renvoie 'moyenne'

Tests (2/4)

Ordre de priorite

f = FilePriorite()
f.ajouter(3, 'basse')
f.ajouter(1, 'haute')
f.ajouter(2, 'moyenne')
assert f.retirer() == 'haute'
assert f.retirer() == 'moyenne'

Est vide

f = FilePriorite()
assert f.est_vide() == True
f.ajouter(1, 'x')
assert f.est_vide() == False

+ 0 tests cachés

Indices (3 disponibles)

Solution officielle

class FilePriorite:
    def __init__(self):
        self._éléments = []

    def ajouter(self, priorite, tache):
        self._éléments.append((priorite, tache))
        self._éléments.sort()

    def retirer(self):
        if self.est_vide():
            raise IndexError('File de priorite vide')
        priorite, tache = self._éléments.pop(0)
        return tache

    def est_vide(self):
        return len(self._éléments) == 0

← Pile pour vérifier les parentheses Somme récursive d'une liste →

solution.py

Bravo!

File de priorite

Tests (2/4)

Indices (3 disponibles)

Solution officielle