Tas et files de priorité

Un tas est une structure qui garde toujours le plus petit élément tout en haut, prêt à être pris. Il sert à construire une file de priorité, où l’on sert d’abord l’élément le plus urgent.

Le service informatique d’une université reçoit des tickets : une panne du réseau, une imprimante, un mot de passe oublié. Il doit traiter d’abord le plus urgent, pas le plus ancien.

Un tas est un arbre binaire rempli niveau par niveau, de gauche à droite, sans trou. Sa règle : chaque parent est plus petit que ses deux enfants.

Le plus petit élément est donc toujours à la racine. Les deux enfants ne sont pas rangés entre eux : le plus petit peut être à gauche ou à droite.

Un tas n’a pas de trou, donc une liste suffit. La racine est à l’indice 0. Le parent de l’indice i est à l’indice (i - 1) // 2.

Les enfants de l’indice i sont aux indices 2 × i + 1 et 2 × i + 2. Un calcul d’indice remplace le lien. La commande suivante calcule le parent de l’indice 6, puis les enfants de l’indice 2 : elle affiche 2, 5 et 6.

python3 -c "print((6 - 1) // 2, 2 * 2 + 1, 2 * 2 + 2)"

Pour ajouter une valeur, on la pose à la première place libre, tout en bas. Tant qu’elle est plus petite que son parent, on l’échange avec lui : elle remonte.

Elle s’arrête dès que son parent est plus petit, ou à la racine. Il y a au plus un échange par niveau.

Le plus petit est à la racine. On le retire, puis on met à sa place le dernier élément de la liste. Il est sans doute trop grand.

Tant qu’il est plus grand que son plus petit enfant, on l’échange avec cet enfant : il descend.

import heapq

# La file de priorité d’un service informatique : le plus petit nombre passe d’abord.
tickets = []
heapq.heappush(tickets, [3, "mot de passe"])
heapq.heappush(tickets, [1, "panne du réseau"])
heapq.heappush(tickets, [2, "imprimante"])

while len(tickets) > 0:
    ticket = heapq.heappop(tickets)
    print(ticket[0], ticket[1])
# Ajoutez un ticket de priorité 1 à la liste, puis relancez.

Chaque échange change de niveau, donc une opération coûte au plus la hauteur du tas. Pour 1 000 éléments, c’est environ 10 étapes. Pour un million, environ 20.

Une liste non triée ajoute vite, mais trouver le plus petit demande de tout regarder. Le tas équilibre les deux.

Python propose le module heapq, qui range un tas dans une liste comme nous venons de le faire. La première commande ajoute 5, 3, 8 puis 1, retire le plus petit, et affiche ce qui reste.

La seconde range d’un coup la liste 5, 3, 8, 1 en tas et l’affiche.

python3 -c "import heapq; t = []; [heapq.heappush(t, x) for x in [5, 3, 8, 1]]; print(heapq.heappop(t), t)"

python3 -c "import heapq; t = [5, 3, 8, 1]; heapq.heapify(t); print(t)"

Poussez dans un tas tous les nombres d’une liste, puis retirez-les un à un : ils sortent triés. C’est le tri par tas.

Estimez le nombre d’étapes pour 1 000 nombres, puis comparez avec l’insertion de chaque nombre dans une liste triée.