2.38. Files de priorité¶

Une file de priorité est un conteneur qui sait toujours lequel de ses éléments est le plus petit (ou le plus grand) sans avoir à trier l’ensemble. heapq en implémente une en MicroPython à l’aide d’une simple list comme stockage et d’un algorithme arborescent appelé tas-min qui maintient le plus petit élément à l’index 0.

2.38.1. Le modèle mental¶

Un tas-min est une liste organisée de telle sorte que l’élément à chaque index est inférieur ou égal aux éléments aux index 2*i + 1 et 2*i + 2. Cette organisation rend trois opérations peu coûteuses :

Trouver le plus petit élément – il se trouve à heap[0]. Une simple consultation d’index, sans parcours.
Ajouter un élément – il remonte à travers l’arbre, en se comparant à un parent par niveau. Mille éléments représentent environ dix comparaisons ; un million, environ vingt.
Retirer le plus petit élément – le même parcours en sens inverse, avec la même poignée de comparaisons.

La liste n’est pas triée. L’itérer renvoie les éléments dans un ordre arbitraire. Seul heap[0] est garanti d’être le minimum.

2.38.2. Les trois fonctions sous MicroPython¶

Le module heapq de MicroPython expose exactement trois fonctions :

heapq.heappush() – insère un élément en préservant l’invariant du tas.
heapq.heappop() – retire et renvoie le plus petit élément.
heapq.heapify() – réorganise sur place une liste existante en tas.

C’est toute la surface disponible. Les fonctions heappushpop, heapreplace, nlargest, nsmallest et merge de CPython n’existent pas ; les modèles ci-dessous montrent comment construire les plus courantes à la main.

En partant de zéro

>>> import heapq
>>> heap = []
>>> heapq.heappush(heap, 5)
>>> heapq.heappush(heap, 1)
>>> heapq.heappush(heap, 3)
>>> heap
[1, 5, 3]
>>> heapq.heappop(heap)
1
>>> heapq.heappop(heap)
3
>>> heapq.heappop(heap)
5

En partant de données existantes

>>> samples = [5, 1, 3, 2, 4]
>>> heapq.heapify(samples)
>>> samples
[1, 2, 3, 5, 4]
>>> heapq.heappop(samples)
1

La transformation en tas ne touche chaque élément qu’une seule fois et est nettement plus rapide que d’insérer les mêmes éléments un par un.

2.38.3. Top-N sur un flux¶

Une utilisation naturelle d’une file de priorité : suivre les N plus grands éléments d’un flux que vous ne pouvez lire qu’une seule fois.

L’astuce consiste à conserver un tas-min de taille N. Chaque nouvelle valeur est insérée ; si le tas dépasse N, on supprime le plus petit. Le plus petit se trouve toujours à heap[0], donc une seule comparaison décide de conserver ou d’écarter chaque élément entrant

def top_n_brightest(readings, n):
    heap = []
    for r in readings:
        if len(heap) < n:
            heapq.heappush(heap, r)
        elif r > heap[0]:
            heapq.heappop(heap)
            heapq.heappush(heap, r)
    return sorted(heap, reverse=True)

Le tas ne dépasse jamais N, donc chaque valeur entrante coûte la même poignée de comparaisons quelle que soit la longueur du flux. Le sorted final est la seule étape dont le coût dépend directement de N.

2.38.4. Événements planifiés¶

Une file de priorité de tuples (deadline, payload) est la forme standard d’un planificateur d’événements. Les tuples se comparent lexicographiquement, de sorte que le tuple avec la plus petite échéance remonte automatiquement au sommet

import heapq
import time

queue = []
heapq.heappush(queue, (time.time() + 5, 'check sensors'))
heapq.heappush(queue, (time.time() + 1, 'blink LED'))
heapq.heappush(queue, (time.time() + 3, 'send heartbeat'))

while queue:
    deadline, task = queue[0]
    now = time.time()
    if now < deadline:
        time.sleep(deadline - now)
    heapq.heappop(queue)
    run(task)

Si deux événements partagent la même échéance, la comparaison de tuples passe au deuxième élément. Pour des charges utiles qui ne sont pas naturellement comparables, ajoutez un compteur comme deuxième élément du tuple afin de forcer un ordre stable

counter = 0
def schedule(deadline, task):
    global counter
    counter += 1
    heapq.heappush(queue, (deadline, counter, task))

Désormais le comportement « plus petite échéance d’abord » est préservé, les égalités sont départagées par le compteur de sorte que les tâches planifiées en premier s’exécutent d’abord, et task n’a pas besoin d’être comparable.

2.38.5. Ce que `heapq` ne vous offre pas¶

Quelques modèles qui semblent devoir fonctionner, mais qui n’en font rien :

Itérer avec for x in heap ne donne pas une sortie triée – l’ordre sous-jacent de la liste est l’agencement arborescent du tas. Pour consommer le tas dans l’ordre, utilisez heappop jusqu’à ce qu’il soit vide.
Il n’existe aucun moyen de modifier la priorité d’un élément déjà présent dans le tas. La solution de contournement standard consiste à insérer la nouvelle priorité comme nouvelle entrée et à marquer l’ancienne comme annulée (en l’ignorant lorsqu’elle ressort).
Le tas stocke des références vers ses éléments, pas des copies. Modifier un élément après son insertion peut rompre l’invariant du tas. Utilisez des valeurs immuables (nombres, tuples) comme clé de comparaison.

Un tas-min sur une simple liste est l’outil approprié pour toute question du type « quel est le plus petit » ou « quel est le plus urgent » sur un petit appareil embarqué. Trois fonctions, une liste, et le tas s’occupe du reste.