\(\newcommand{\ds}{\displaystyle}\) \(\newcommand{\Frac}{\ds\frac}\) \(\renewcommand{\r}{\mathbb{ R}}\) \(\newcommand{\C}{\mathbb{ C}}\) \(\newcommand{\n}{\mathbb{ N}}\) \(\newcommand{\z}{\mathbb{ Z}}\) \(\newcommand{\Q}{\mathbb{ Q}}\) \(\newcommand{\N}{\mathbb{ N}}\) \(\newcommand{\n}{\mathbb{ N}}\) \(\newcommand{\ol}{\overline}\) \(\newcommand{\abs}[1]{\left| \,{#1} \right|}\) \(\newcommand{\pv}{\;;\;}\) \(\newcommand{\ens}[1]{\left\{ {#1} \right\}}\) \(\newcommand{\mens}[1]{\setminus\left\{ {#1} \right\}}\) \(\newcommand{\Par}[1]{\left({#1}\right)}\) \(\newcommand{\pe}[1]{\left\lfloor {#1} \right\rfloor}\) \(\newcommand{\trans}[1]{\,^t\!{#1}}\)

Les files de priorité¶

Rappels sur les files de priorité¶

On dispose d’une collection dynamique d’objets comparables (tels que des entiers) : des objets peuvent être ajoutés ou retirés à la collection. On cherche à maintenir de manière efficace la connaissance du plus petit élément de la collection d’objets.

Une simple liste ne permet pas de parvenir à cette tâche : si on ajoute des objets à la collection, on peut certes mettre à jour le minimum mais si on retire le minimum il faut ré-examiner tous les éléments un à un pour déterminer le nouveau minimum.

Une file de priorité est justement une structure de données capable de maintenir de manière efficace le plus petit élément de la collection d’objets. Quand il est dit « efficacement », il est attendu que la recherche soit en \(O(1)\) et l’extraction soit, au pire, en \(O(\log n)\) où \(n\) est le nombre d’éléments.

Ce type de structure sert par exemple dans

l’algorithme de Dijkstra de recherche d’un plus court chemin dans un graphe valué
l’algorithme de Prim de recherche d’un arbre couvrant de poids minimal.

Ainsi, dans l’algorithme de Dijkstra, le gain peut être vraiment substantiel : pour un graphe de quelques milliers de sommets, l’amélioration peut être d’un facteur 10.

La structure de file de priorité permet aussi de trier une liste de nombres de manière asymptotiquement optimale.

Cette structure de données est connue sous le nom anglais priority queue. Le terme de tas binaire (binary heap queue) est réservé à une implémentation particulière de cette structure de données (sous la forme d’un arbre binaire équilibré).

Pour simplifier l’exposé, on va supposer que les éléments de la file de priorité sont des entiers dont on cherche à connaître le minimum alors que la structure évolue. Une file de priorité peut se représenter par un tas binaire : il s’agit d’un arbre binaire dont les sommets sont les entiers de la structure et en sorte que la racine de tout sous-arbre soit inférieure à tous les éléments du sous-arbre. En particulier, la racine de l’arbre est le plus petit de tous les éléments de la structure (l’élément prioritaire). En outre, les feuilles de l’arbre se répartissent sur deux niveaux consécutifs au plus. Ainsi, le nombre de niveaux d’une file de priorité sur \(n\) éléments est d’au plus \(\log_2(n)\).

Deux opérations sont associées à une file de priorité :

l’insertion d’un nouvel élément (opération en général désignée par push) ;
l’extraction du minimum via la suppression de la racine de l’arbre (opération en général désignée par pop) ;

Une fois achevée une opération d’insertion ou de suppression du minimum, la structure doit rester un arbre de priorité ce qui nécessite de réorganiser l’arbre. Ces opérations de réorganisation ne sont pas difficiles à comprendre mais elles ne sont pas triviales et demandent du soin à être programmées. Voir par exemple :

Sedgewick, Wayne : priority queue
Wikipedia : opérations sur un tas binaire
la série de trois vidéos Introduction to a Heap.

Il existe d’autres structures de données implémentant les opérations d’une file de priorité. En comparaison, le tas binaire a de bonnes performances. Toutefois, comme le montre un tableau de performances, un tas de Fibonacci a une meilleure complexité pour l’insertion d’un élément qui est en \(O(1)\) au lieu de \(O(\log n)\) pour une file de priorité.

Les files de priorité en Python¶

La bibliothèque standard Python propose la structure de données file de priorité via le module heapq. L’implémentation en CPython de ce module est écrite en C et non en Python, ce qui lui assure une bonne efficacité d’exécution.

Voici un exemple simple d’utilisation d’une file de priorité avec le module heapq :

from heapq import heappush, heappop
from random import randrange

n=6
L=[]
for _ in range(n):
    x=randrange(10,100)
    heappush(L, x)
    print(x, L)

print()

for _ in range(n):
    print(heappop(L))

68 [68]
19 [19, 68]
99 [19, 68, 99]
70 [19, 68, 99, 70]
66 [19, 66, 99, 70, 68]
34 [19, 66, 34, 70, 68, 99]

19
34
66
68
70
99

Ligne 7-8 : on génère 6 entiers aléatoires qu’on place successivement dans une liste L.
Ligne 8 : la fonction heappush insère l’élément et réorganise la structure de données pour qu’elle reste une file de priorité.
Ligne 15-20 : la représentation sous forme de liste de la file de priorité après chaque insertion.
lignes 13-14 et 22-27 : on retire à chaque étape la racine de l’arbre binaire et on obtient les éléments dans l’ordre croissant.

Dans le code ci-dessus, les éléments sont entrés dans la file un à un à l’aide de la fonction heappush. Il est également possible de transformer une liste en une file de priorité grâce à la fonction heapify :

from heapq import heapify, heappop
from random import randrange

n=6
L=[randrange(10,100) for _ in range(n)]
print(L)

heapify(L)

for _ in range(n):
    print(heappop(L))

[65, 31, 68, 47, 57, 48]
31
47
48
57
65
68

L’instruction de la ligne 8 est évidemment essentielle, c’est elle qui organise la liste en file de priorité. Si cette instruction est omise le classement obtenu lignes 13-18 devient incorrect :

from heapq import heapify, heappop
from random import randrange

n=6
L=[randrange(10,100) for _ in range(n)]
print(L)

for _ in range(n):
    print(heappop(L))

[57, 42, 27, 35, 56, 29]
57
27
29
35
42
56

Une file de priorité Python accepte n’importe quel type d’objets à condition que Python sache les comparer. Ainsi, une file de priorité pourra accepter des listes de listes mais pas des objets parmi lesquels se trouveraient un entier et une chaîne de caractère :

from heapq import heappush, heappop

L=[]
heappush(L, 5)
heappush(L, 'z')
print(L)

Traceback (most recent call last):
  File "test.py", line 5, in <module>
    heappush(L, 'z')
TypeError: unorderable types: str() < int()

Exercice : liste des puissances croissantes¶

On dit qu’un entier est une puissance s’il peut s’écrire de la forme \(\mathtt{x^n}\) où \(\mathtt{x>1}\) est un entier et \(\mathtt{n\geq 2}\) est un exposant entier.

On donne un rang \(\mathtt{N>0}\) et on demande d’écrire un code qui donne la \(\mathtt{N^{e}}\) puissance \(\mathtt{P}\) dans l’ordre strictement croissant. Par exemple, si \(\mathtt{N=8}\) alors la liste croissante des \(\mathtt{N}\) premières puissances est :

[4, 8, 9, 16, 25, 27, 32, 36]

et donc la \(\mathtt{8^e}\) puissance vaut \(\mathtt{P=36}\).

On placera dans une file de priorité des tuples de la forme (x**n, (x, n)). Vérifier que la millionième puissance est \(\mathtt{P=979848556129}\).

Concernant la suite des puissances, on pourra consulter l’article de OEIS ou encore Wikipedia: powerful numbers.

Une implémentation en Python d’une file de priorité¶

Une file de priorité, bien que représentée par un arbre binaire, peut aussi être astucieusement représentée par une liste, cf. les vidéos citées plus haut ou Sedgewick, Wayne.

Si vous vous intéressez à l’implémentation de files de priorité (par exemple, vous voulez en écrire une en C, en C++, en Cython ou encore en Numba + Numpy), le code ci-dessous peut vous aider à comprendre le fonctionnement de push et pop :

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

    def push(self, x):
        t=self.t
        t.append(x)
        k=len(t)-1
        while k:
            m=(k-1)//2
            if t[k]<t[m]:
                t[k], t[m]=t[m], t[k]
                k=m
            else:
                break
    def pop(self):
        t=self.t
        if not t:
            raise IndexError("pop from empty heap")
        if len(t)==1:
            return t.pop()
        root=t[0]
        t[0]=t.pop()
        k=0

        while True:
            L=[i for i in [2*k+1, 2*k+2] if i<len(t)]
            if not L:
                break
            mini=min(t[i] for i in L)
            if t[k]<mini:
                break
            for i in L:
                if t[i]==mini:
                    t[i],t[k]=t[k], t[i]
                    k=i
                    break

        return root


from random import randrange


n=6
h=heap()


for _ in range(n):
    x=randrange(10,100)
    h.push(x)
    print(x, h.t)

print()

for _ in range(n):
    print(h.pop())

qui affiche

18 [18]
45 [18, 45]
66 [18, 45, 66]
70 [18, 45, 66, 70]
26 [18, 26, 66, 70, 45]
15 [15, 26, 18, 70, 45, 66]

15
18
26
45
66
70