Files de priorité : le tas binaire

19.1 Introduction et motivation

Une file de priorité est une collection d'où l'on extrait toujours l'élément le plus prioritaire (ici, le plus petit) — comme un service d'urgences traite d'abord les cas les plus graves. C'est l'outil qui manquait au chapitre 16 : Dijkstra a besoin, à chaque étape, du sommet non traité de plus petite distance. Avec une liste ou un tableau, le trouver coûte $\Theta (n)$ ; une file de priorité bien faite le donne en $\Theta (\log n)$.

La structure reine pour cela est le tas binaire, un arbre binaire presque complet rangé… dans un simple tableau (chapitre 5). Ce chapitre l'implémente — insertion, extraction du minimum, construction — puis en tire le tri par tas (chapitre 9) et une version efficace de Dijkstra (chapitre 16).

19.2 Le tas binaire