Une file de priorité répond rapidement à une question : quel élément est le plus urgent en ce moment ? Un tas est la structure standard qui la réalise.
Forme et règle
Un tas binaire est un arbre binaire complet stocké dans un tableau. Dans un tas-min, chaque parent est inférieur ou égal à ses enfants, donc le plus petit élément se trouve à la racine. Pour le nœud d’indice i, les enfants sont aux indices 2*i* + 1 et 2*i* + 2, et le parent à (i − 1) // 2. Aucun pointeur n’est nécessaire.
Deux opérations font tout le travail
Pour insérer, on place le nouvel élément à la fin puis on le fait remonter tant qu’il est plus petit que son parent. Pour retirer le minimum, on prend la racine, on met le dernier élément à sa place, puis on le fait descendre en l’échangeant avec son plus petit enfant jusqu’à ce que la règle soit rétablie. Chaque opération parcourt au plus la hauteur de l’arbre : O(log n). Lire le minimum est en O(1).
Où l’on rencontre les tas
- L’algorithme de Dijkstra et A* utilisent une file de priorité pour choisir le prochain nœud.
- Les ordonnanceurs l’emploient pour exécuter d’abord la tâche la plus prioritaire.
- Les problèmes de type « k plus grands » gardent un tas de taille k.
- Le tri par tas trie en O(n log n).
Un tas n’est pas une liste triée
Un tas garantit seulement que la racine est le minimum. Le reste du tableau n’est que partiellement ordonné. Pour lire tous les éléments dans l’ordre, il faut les retirer un par un. Construire un tas à partir de n éléments existants est possible en O(n).
Une astuce pratique
Pour trouver les k plus grandes valeurs d’un flux, gardez un tas-min de taille k. Quand une nouvelle valeur dépasse la plus petite du tas, remplacez-la. Le tas contient toujours les k meilleures valeurs vues jusqu’ici.
Pour aller plus loin
Retrouvez le traitement complet, les exemples et les exercices dans Les algorithmes en clair.
Adapté de Les algorithmes en clair, publié par Choral Software. Texte de l’article et exemples originaux © 2026 Choral Software. Tous droits réservés.