02 — File de priorité et tas binaire

Ce que tu vas apprendre

• Ce qu'est une file de priorité et pourquoi un tableau trié ne suffit pas
• Le tas binaire : invariant, stockage dans un tableau
• Insertion et extraction en O(log n)
• Les usages réels : Dijkstra, top-k, ordonnancement

Prérequis

• 01 — Piles et files
• Le tri par tas de la série Tri (utile mais pas obligatoire)

Une file de priorité sert les éléments par ordre d'importance, pas par ordre d'arrivée. On veut toujours extraire l'élément de plus haute (ou plus basse) priorité, et pouvoir en insérer de nouveaux à tout moment. C'est un besoin très courant : l'ordonnanceur du système qui choisit le prochain processus, l'algorithme de Dijkstra qui prend le nœud le plus proche, ou le maintien des K plus grandes valeurs d'un flux.

Pourquoi pas un simple tableau trié

On pourrait garder un tableau trié : l'élément prioritaire est alors au bout, extraction en O(1). Mais l'insertion d'un nouvel élément à sa place coûte O(n), car il faut décaler. À l'inverse, un tableau non trié insère en O(1) mais cherche le prioritaire en O(n). Aucun des deux n'est bon sur les deux opérations.

Le tas binaire offre le compromis : insertion et extraction du prioritaire en O(log n). C'est ce qui en fait l'implémentation standard d'une file de priorité.

Le tas binaire

Un tas binaire (vu brièvement dans la série Tri) est un arbre binaire qui respecte un invariant simple : chaque nœud est prioritaire sur ses enfants. Dans un min-heap, chaque parent est inférieur ou égal à ses enfants, donc le minimum est toujours à la racine. C'est l'invariant qui garantit l'accès en O(1) à l'élément prioritaire.

L'astuce essentielle : le tas se range dans un tableau, sans pointeurs, grâce aux indices.

• enfants de l'index i : 2i + 1 et 2i + 2
• parent de l'index i : (i - 1) / 2 (division entière)

Les deux opérations

Insertion. On ajoute le nouvel élément en fin de tableau, puis on le fait remonter tant qu'il est plus prioritaire que son parent (sift up). Le chemin vers la racine fait au plus log n étapes.

Extraction du minimum. On retire la racine (le minimum), on met le dernier élément à sa place, puis on le fait redescendre tant qu'un enfant est plus prioritaire (sift down). Là aussi, O(log n).

typescriptclass MinHeap {
  private h: number[] = [];

  inserer(x: number): void {
    this.h.push(x);
    let i = this.h.length - 1;
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (this.h[parent] <= this.h[i]) break;
      [this.h[parent], this.h[i]] = [this.h[i], this.h[parent]];
      i = parent;
    }
  }

  extraireMin(): number | undefined {
    if (this.h.length === 0) return undefined;
    const min = this.h[0];
    const dernier = this.h.pop()!;
    if (this.h.length > 0) {
      this.h[0] = dernier;
      this.tamiser(0);
    }
    return min;
  }

  private tamiser(i: number): void {
    const n = this.h.length;
    while (true) {
      let petit = i;
      const g = 2 * i + 1, d = 2 * i + 2;
      if (g < n && this.h[g] < this.h[petit]) petit = g;
      if (d < n && this.h[d] < this.h[petit]) petit = d;
      if (petit === i) break;
      [this.h[i], this.h[petit]] = [this.h[petit], this.h[i]];
      i = petit;
    }
  }

  get taille(): number { return this.h.length; }
}

En Python, la bibliothèque standard fournit heapq, un min-heap sur liste, ce qui évite de réécrire le tas.

pythonimport heapq

tas = []
heapq.heappush(tas, 5)   # O(log n)
heapq.heappush(tas, 1)
heapq.heappush(tas, 3)
heapq.heappop(tas)       # O(log n), renvoie 1 (le min)

Les usages

Les cas d'usage sont nombreux :

• Dijkstra (série Graphes) : à chaque étape, on extrait le nœud non visité le plus proche. Une file de priorité fait passer l'algorithme de O(n²) à O((n + arêtes) log n).
• Top-k : pour garder les K plus grands éléments d'un flux, on maintient un min-heap de taille K. Chaque nouvel élément est comparé à la racine (le plus petit des K) en O(1), inséré en O(log K) s'il est plus grand. On traite un flux énorme en mémoire O(K).
• Ordonnancement : tâches avec priorités, événements à traiter dans l'ordre temporel (simulation à événements discrets).
• Tri par tas : vu dans la série Tri, c'est l'application directe du tas à l'ordonnancement complet.

pythondef top_k(flux, k):
    tas = []
    for x in flux:
        if len(tas) < k:
            heapq.heappush(tas, x)
        elif x > tas[0]:           # plus grand que le plus petit des k
            heapq.heapreplace(tas, x)
    return sorted(tas, reverse=True)

Le tas est l'exemple parfait d'une structure conçue pour une opération précise (servir le prioritaire) qu'aucune structure généraliste ne fait bien. L'article suivant revient à une structure linéaire dont la série Complexité parlait sans la construire : la liste chaînée.

Sources

• Williams, J. W. J. (1964). Algorithm 232: Heapsort. Communications of the ACM, 7(6). (Origine du tas binaire)
• Cormen, T. H., et al. (2009). Introduction to Algorithms (3rd ed.), Chapitre 6 "Heapsort" et Section 6.5 "Priority Queues". MIT Press.
• Python Software Foundation. heapq — Heap queue algorithm. docs.python.org/3/library/heapq.html
• Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.), Section 2.4 "Priority Queues". Addison-Wesley.