Les files de priorité

Les files de priorités sont des structures de données généralisant les files et piles. Dans cet article, nous présentons leur fonctionnement. Le détail d’implémentation est plus compliqué que pour les autres structures, et est donc proposé aux plus motivés !

Les files de priorité sont disponibles dans Python notamment grâce au module queue (voir ici) ou heapq (voir ici).

Présentation

A l’instar des files et des piles, les files de priorité sont des structures permettant d’ajouter ou de retirer des éléments selon une certaine règle. Quand on retire un élément d’une file ou d’une pile, l’élément renvoyé dépend de sa date d’insertion dans la structure. Comme on l’a vu précédemment, ce qui différencie file et pile est la fonction d’insertion (à la fin ou au début de la liste). En revanche, la fonction d’extraction est identique (prendre la tête de liste).

Maintenant, imaginons une structure de données S munie d’une fonction in ajoutant un élément à S en lui associant un entier (qu’on appellera étiquette), et une fonction out renvoyant l’élément de S d’étiquette maximum. On a les résultats suivants :

Si in est une fonction qui associe à chaque élément inséré une étiquette dont la valeur augmente avec le temps, alors la structure S munie des fonctions in et out est une pile. En effet, comme le dernier élément ajouté a une étiquette plus haute que les autres, c’est celui qui sera choisi par la fonction out.
Si in est une fonction qui associe à chaque élément inséré une étiquette dont la valeur diminue avec le temps, alors la structure S munie des fonctions in et out est une file. Ici aussi, la fonction out cherchera à retirer l’élément d’étiquette la plus haute, qui dans ce cas sera le plus ancien.

D’une manière générale, on appelle file de priorité une structure S munie d’une fonction d’insertion in, et d’une fonction d’extraction out. En général, out est soit une fonction retirant l’élément de plus grande étiquette, soit une fonction retirant celui de plus petite étiquette. Tout le challenge est donc de trouver une fonction in qui répond à vos besoins !

Pour récapituler, voici quelques files de priorité classiques :

	out
in

Etiquette min

Etiquette max

Augmente avec le temps

File

Pile

Diminue avec le temps

Pile

File

Fonction quelconque

Tas-min

Tas-max

Note : Cette définition à l’aide de ces quelques fonctions in et out n’est pas unique. On pourrait aussi définir une file de priorité utilisant des fonctions in et out bien plus complexes. Le point commun à toute définition est que l’ordre d’insertion et de retrait de la structure est important, et doit être représenté par les étiquettes.

Implémentation naïve d’une file de priorité à l’aide d’une liste

Une façon simple d’implémenter une file de priorité est d’utiliser une liste. Cette liste stocke des couples (élément, étiquette). Nous montrons ici comment créer un tas-min à l’aide d’une liste.

Création

Pour créer une file de priorité à l’aide d’une liste, on créé tout simplement une liste vide :

def priorityQueue () :
    return []

1 2	def priorityQueue () : return []

Test de vacuité

Pour tester si une file de priorité est vide, il suffit de la comparer avec la liste vide :

def empty (queue) :
    return queue == []

1 2	def empty (queue) : return queue == []

Insertion

Pour l’insertion et la récupération, un choix s’offre à nous :

Soit faire le travail coûteux au moment de l’insertion, par exemple en maintenant notre liste triée par ordre croissant d’étiquettes :

def put (element, label, queue) :
    for i in range(len(queue)) :
        e, l = queue[i]
        if label < l :
            return queue[:i] + [(element, label)] + queue[i:]
    return queue + [(element, label)]

def put (element, label, queue) :

for i in range(len(queue)) :

e, l = queue[i]

if label < l :

return queue[:i] + [(element, label)] + queue[i:]

return queue + [(element, label)]

Soit le faire au moment de la récupération, en cherchant l’élément d’étiquette la plus petite. On ajoute donc simplement l’élément à la liste :

def put (element, label, queue) : return queue + [(element, label)]

1
2

def put (element, label, queue) :
return queue + [(element, label)]

Récupération

Pour récupérer l’élément ayant la plus petite étiquette dans cette file de priorité et la file de priorité restante, on se retrouve donc avec deux versions, selon le scénario choisi pour l’insertion :

Pour la version 1. :

# The queue is supposed nonempty def get (queue) : return queue[0], queue[1:]

1
2
3

# The queue is supposed nonempty
def get (queue) :
return queue[0], queue[1:]

Pour la version 2. :

# The queue is supposed nonempty
def get (queue) :
    minElement, minLabel = queue[0]
    minIndex = 0
    for i in range(len(queue)) :
        e, l = queue[i]
        if l < minLabel :
            minLabel = l
            minElement = e
            minIndex = i
    return (minElement, minLabel), queue[:minIndex] + queue[minIndex + 1:]

# The queue is supposed nonempty

def get (queue) :

minElement, minLabel = queue[0]

minIndex = 0

for i in range(len(queue)) :

e, l = queue[i]

if l < minLabel :

minLabel = l

minElement = e

minIndex = i

return (minElement, minLabel), queue[:minIndex] + queue[minIndex + 1:]

Tests

Pour tester nos fonctions, exécutons les quelques commandes suivantes :

# Structure preparation
queue = priorityQueue()
queue = put("five", 5, queue)
queue = put("three", 3, queue)
queue = put("eight", 8, queue)

# [('three', 3), ('five', 5), ('eight', 8)] if solution 1. is chosen
# [('five', 5), ('three', 3), ('eight', 8)] if solution 2. is chosen
print(repr(queue))

# "three", then "five", then "eight"
while not empty(queue) :
    (e, l), queue = get(queue)
    print(e)

# []
print(repr(queue))

# Structure preparation

queue = priorityQueue()

queue = put("five", 5, queue)

queue = put("three", 3, queue)

queue = put("eight", 8, queue)

# [('three', 3), ('five', 5), ('eight', 8)] if solution 1. is chosen

# [('five', 5), ('three', 3), ('eight', 8)] if solution 2. is chosen

print(repr(queue))

# "three", then "five", then "eight"

while not empty(queue) :

(e, l), queue = get(queue)

print(e)

# []

print(repr(queue))

Complexité

Le problème avec cette implémentation à l’aide d’une liste est la complexité des opérations. Selon la version, soit l’insertion soit la récupération requiert de parcourir la liste, amenant à un nombre d’opérations élémentaires au moins proportionnel à la taille de la liste (O(n), avec n le nombre d’éléments dans la liste). En pratique cette complexité est beaucoup trop grande.

Implémentation à l’aide d’un arbre binaire équilibré

En prérequis pour comprendre cette partie, il vous faut lire attentivement la fiche sur les arbres.

Au lieu d’utiliser une liste, on propose d’utiliser un arbre binaire équilibré ayant les propriétés suivantes :

À chaque nœud de l’arbre est associé un couple (élément, étiquette). Cette propriété permet de faire le lien entre l’arbre et les éléments à stocker/extraire.
Tout parent a deux fils, sauf si le nombre total d’éléments dans la file de priorité est pair auquel cas un unique nœud n’a qu’un fils et tous les autres en ont deux. Remarque : On aurait aussi pu considérer des arbres ternaires/quaternaires/etc. Plus le nombre de fils augmente, plus la complexité de l’opération d’insertion diminue, mais plus celle de l’extraction augmente.
L’arbre est équilibré. Cette propriété garantit que l’arbre n’a pas une forme similaire à une longue chaîne, en faisant de fait une sorte de liste, perdant donc tout l’intérêt d’utiliser des arbres.
L’étiquette d’un parent est toujours plus petite que celle de ses fils. Cette propriété essentielle garantit que le nœud d’étiquette minimale est toujours à la racine.

Création

Pour initialiser une telle file de priorité, il suffit de rendre l’arbre vide.

Test de vacuité

Pour tester si une file de priorité est vide, on regarder si l’arbre est vide.

Insertion

Pour insérer un élément et son étiquette dans l’arbre, on procède comme suit :

On ajoute le nœud associé à l’élément et son étiquette à la fin de l’arbre, c’est-à-dire :
- Si tous les nœuds parents ont deux nœuds fils, on transforme une feuille de profondeur minimale en parent de ce nouveau nœud
- Si un nœud parent n’a qu’un seul fils, on lui ajoute comme deuxième fils ce nouveau nœud
Si l’étiquette de ce nouveau nœud est plus petite que celle de son parent, on échange les couples (élément, étiquette) du nœud et de son parent
On continue en remontant ainsi dans l’arbre tant que nécessaire

Puisque on ne fait que remplacer des étiquettes présentes dans l’arbre par des étiquettes plus petites, l’arbre obtenu garde les propriétés énoncées si celui de départ les avait.

Récupération

Pour récupérer un élément, on procède ainsi :

On récupère le couple (élément, étiquette) associé à la racine de l’arbre.
À sa place, on met celui associé à l’une des feuilles de profondeur maximale de l’arbre et on supprime le nœud correspondant
Si la nouvelle racine a une étiquette plus grande qu’un de ses fils, on procède à l’échange des couples (élément, étiquette) avec le fils qui a l’étiquette la plus petite.
On recommence en descendant tant que nécessaire

Là aussi, on vérifie facilement que l’arbre obtenu respecte les propriétés énoncées si l’arbre de départ les respectait aussi.

Complexité

La complexité des opérations d’insertion et de récupération requiert de parcourir l’arbre de la racine jusqu’à une feuille de profondeur maximale dans le pire des cas. L’arbre étant binaire, ceci représente log₂(n) opérations, où n est le nombre d’éléments dans la file. On est donc bien moins coûteux qu’avec une liste (où le nombre d’opérations était au moins linéaire en n).

Les files de priorité

Présentation

Implémentation naïve d’une file de priorité à l’aide d’une liste

Création

Test de vacuité

Insertion

Récupération

Tests

Complexité

Implémentation à l’aide d’un arbre binaire équilibré

Création

Test de vacuité

Insertion

Récupération

Complexité

Pour approfondir

Laisser un commentaire Annuler la réponse.