Chapitre 8 — Tas et files de priorité
Organiser les données selon leur priorité et extraire efficacement l’élément prioritaire
| Positionnement dans le parcours — Ce chapitre introduit une structure arborescente compacte, le tas, et son utilisation principale : la file de priorité. Il prépare l’étude du tri par tas, des algorithmes de graphes utilisant une priorité et de l’ordonnancement efficace des tâches. |
Fiche pédagogique du chapitre
Objectifs d’apprentissage
À la fin de ce chapitre, l’étudiant devra être capable de :
- distinguer un tas minimum d’un tas maximum ;
- expliquer pourquoi un tas est un arbre binaire complet ;
- vérifier la propriété d’ordre d’un tas ;
- représenter un tas dans un tableau sans stocker de références ;
- calculer les indices du parent et des deux enfants ;
- insérer un élément et restaurer l’ordre par remontée ;
- extraire l’élément prioritaire et restaurer l’ordre par descente ;
- construire un tas efficacement à partir d’un tableau quelconque ;
- implémenter une file de priorité et analyser le coût de ses opérations ;
- appliquer les tas à l’ordonnancement, aux urgences, aux simulations et au tri.
Prérequis
- Arbres binaires, profondeur, hauteur et arbre complet.
- Tableaux à une dimension et calcul d’indices.
- Boucles, fonctions et procédures.
- Échanges de valeurs dans un tableau.
- Complexités O(1), O(log n), O(n) et O(n log n).
Organisation proposée
Partie | Contenu principal | Durée indicative |
|---|---|---|
| 8.1 | Tas minimum, tas maximum, complétude et propriété d’ordre | 2 h |
| 8.2 | Représentation par tableau et calcul des indices | 2 h |
| 8.3 | Insertion, remontée, extraction, descente et construction | 5 h |
| 8.4 | File de priorité : interface, implémentation et analyse | 2 h |
| Applications | Tâches, urgences, événements et tri par tas | 2 h |
| TD / TP | Traces, correction de tas et implémentation | 4 à 6 h |
Introduction
Une file de priorité ne traite pas nécessairement les éléments dans leur ordre d’arrivée. Elle sélectionne d’abord l’élément ayant la priorité la plus élevée, ou la plus faible selon la convention choisie. Cette abstraction intervient dans les systèmes d’exploitation, les urgences médicales, la simulation, les réseaux et plusieurs algorithmes de graphes.
Le tas binaire constitue une implémentation particulièrement efficace d’une file de priorité. Il combine la forme d’un arbre binaire complet et une propriété d’ordre locale. Sa forme régulière permet de le stocker directement dans un tableau, sans pointeurs entre les nœuds.
| Idée directrice — Le tas ne maintient pas un ordre total entre tous les éléments. Il garantit seulement que la racine est prioritaire et que chaque parent respecte une relation d’ordre avec ses enfants. |
8.1 Notion de tas
8.1.1 Définition générale
Un tas binaire est un arbre binaire complet respectant une propriété d’ordre. La complétude impose la forme de l’arbre ; la propriété d’ordre détermine la relation entre la clé d’un nœud et celles de ses enfants.
Composante | Rôle |
|---|---|
| Arbre binaire complet | Tous les niveaux sont pleins, sauf éventuellement le dernier, rempli de gauche à droite. |
| Propriété d’ordre | Chaque parent est prioritaire par rapport à ses enfants. |
| Racine | Contient toujours l’élément minimum ou maximum selon le type de tas. |
| Hauteur | Pour n éléments, elle est de l’ordre de log₂(n). |
8.1.2 Tas minimum
Dans un tas minimum, la clé de chaque nœud est inférieure ou égale aux clés de ses enfants. La racine contient donc la plus petite clé de toute la structure.
Exemple de tas minimum 3 / \ 8 5 / \ / \ 12 10 17 9 / \ 20 15 |
La propriété est locale : 8 est inférieur à 12 et 10, 5 est inférieur à 17 et 9, et 3 est inférieur à 8 et 5. En revanche, il n’est pas exigé que 8 soit inférieur à 5 ou que 12 soit inférieur à 9.
| Conséquence — Le minimum est accessible en O(1) à la racine, mais rechercher une valeur quelconque reste en O(n) dans le pire cas. |
8.1.3 Tas maximum
Dans un tas maximum, la clé de chaque nœud est supérieure ou égale aux clés de ses enfants. La racine contient alors la plus grande clé.
Exemple de tas maximum 90 / \ 70 80 / \ / \ 45 60 75 30 / \ 10 20 |
Critère | Tas minimum | Tas maximum |
|---|---|---|
| Relation parent-enfant | parent <= enfants | parent >= enfants |
| Élément à la racine | Minimum | Maximum |
| Extraction prioritaire | ExtraireMinimum | ExtraireMaximum |
| Usage typique | Événement le plus proche, coût le plus faible | Tâche la plus urgente, score maximal |
8.1.4 Arbre binaire complet
La forme complète est essentielle. Les nœuds sont ajoutés niveau par niveau et de gauche à droite. Il ne peut donc pas exister un emplacement vide avant un nœud plus à droite au même niveau.
Forme complète et forme non complète Complet : Non complet : A A / \ / \ B C B C / \ / \ / D E F E F |
La structure de gauche peut être représentée sans perte dans un tableau compact. Celle de droite possède des trous et ne respecte pas l’ordre de remplissage.
| Pourquoi cette contrainte ? — Elle garantit une hauteur minimale pour le nombre de nœuds et rend possibles les formules directes reliant un indice à son parent et à ses enfants. |
8.1.5 Propriété d’ordre
La propriété d’ordre est différente de celle d’un arbre binaire de recherche. Un tas ne sépare pas les valeurs plus petites à gauche et plus grandes à droite. Il impose uniquement une relation entre chaque parent et ses enfants.
Structure | Ordre garanti | Recherche d’une clé quelconque | Accès à l’extrême |
|---|---|---|---|
| Arbre binaire de recherche | Sous-arbre gauche < nœud < sous-arbre droit | O(h) | Minimum ou maximum en O(h) |
| Tas minimum | Parent <= enfants | O(n) | Minimum en O(1) |
| Tas maximum | Parent >= enfants | O(n) | Maximum en O(1) |
| Erreur fréquente — Un parcours infixe d’un tas ne produit pas nécessairement une séquence triée. |
8.1.6 Vérification d’un tas
Pour vérifier un tas, il faut contrôler sa forme complète et comparer chaque nœud interne à ses enfants existants. Dans une représentation par tableau compact, la complétude est déjà garantie ; il reste à vérifier la propriété d’ordre.
Pseudo-code — Vérifier un tas minimum Fonction EstTasMinimum(T, n) : Booleen Pour i allant de 0 à (n div 2) - 1 Faire gauche <- 2 * i + 1 droite <- 2 * i + 2 Si gauche < n ET T[i] > T[gauche] Alors Retourner FAUX FinSi Si droite < n ET T[i] > T[droite] Alors Retourner FAUX FinSi FinPour Retourner VRAI FinFonction Les feuilles commencent à l’indice n div 2 ; elles n’ont pas besoin d’être vérifiées. |
8.2 Représentation par tableau
8.2.1 Principe
Les nœuds d’un tas sont stockés dans l’ordre du parcours en largeur : racine, niveau 1, niveau 2, etc. Comme l’arbre est complet, les cases du tableau sont contiguës et aucun marqueur de case vide n’est nécessaire.
Correspondance entre arbre et tableau Arbre : Tableau (indices à partir de 0) 3 Indice : 0 1 2 3 4 5 6 7 8 / \ Valeur : 3 8 5 12 10 17 9 20 15 8 5 / \ / \ 12 10 17 9 / \ 20 15 |
Cette représentation utilise uniquement le tableau et une variable indiquant le nombre d’éléments présents. Les liens parent-enfant sont calculés à partir des indices.
8.2.2 Calcul des indices avec une numérotation à partir de 0
Relation | Formule | Condition d’existence |
|---|---|---|
Parent de i | (i - 1) div 2 | i > 0 |
Enfant gauche de i | 2i + 1 | 2i + 1 < n |
Enfant droit de i | 2i + 2 | 2i + 2 < n |
Premier indice d’une feuille | n div 2 | Indices n div 2 à n - 1 |
Dernier nœud interne | (n div 2) - 1 | n >= 2 |
Pour le nœud d’indice 1 contenant 8, l’enfant gauche est à l’indice 3, l’enfant droit à l’indice 4 et le parent à l’indice 0.
8.2.3 Calcul des indices avec une numérotation à partir de 1
Certains ouvrages laissent la case 0 inutilisée. Les formules deviennent alors plus simples, mais une case mémoire est perdue.
Relation | Formule pour un indice i >= 1 |
|---|---|
Parent | i div 2 |
Enfant gauche | 2i |
Enfant droit | 2i + 1 |
Racine | Indice 1 |
| Convention du chapitre — Les pseudo-codes utilisent une numérotation à partir de 0, courante dans les langages C, Java et Python. |
8.2.4 Parent, enfant gauche et enfant droit
Les relations d’indices permettent d’accéder en temps constant au voisinage structurel d’un nœud. Aucune référence explicite n’est stockée.
Pseudo-code — Fonctions d’indices Fonction IndiceParent(i) : Entier Retourner (i - 1) div 2 FinFonction
Fonction IndiceGauche(i) : Entier Retourner 2 * i + 1 FinFonction
Fonction IndiceDroit(i) : Entier Retourner 2 * i + 2 FinFonction |
Indice i | Valeur | Parent | Enfant gauche | Enfant droit |
|---|---|---|---|---|
0 | 3 | Aucun | 1 : 8 | 2 : 5 |
1 | 8 | 0 : 3 | 3 : 12 | 4 : 10 |
2 | 5 | 0 : 3 | 5 : 17 | 6 : 9 |
3 | 12 | 1 : 8 | 7 : 20 | 8 : 15 |
4 | 10 | 1 : 8 | Aucun | Aucun |
8.2.5 Avantages et limites de la représentation par tableau
Aspect | Avantages | Limites |
|---|---|---|
| Mémoire | Pas de pointeurs ; stockage compact. | Une capacité doit être gérée si le tableau est statique. |
| Accès structurel | Parent et enfants en O(1). | Pas d’accès direct à une clé quelconque. |
| Localité | Cases contiguës favorables au cache processeur. | Redimensionnement parfois nécessaire. |
| Forme | La complétude est garantie par le remplissage contigu. | Ne représente efficacement que des arbres complets. |
| Implémentation | Algorithmes simples par échanges d’indices. | Les formules dépendent de la convention 0 ou 1. |
8.3 Opérations
8.3.1 Insertion
Pour conserver la forme complète, le nouvel élément est ajouté à la première case libre, donc à la fin du tableau. Cette position respecte la structure mais peut violer la propriété d’ordre. Une remontée est alors nécessaire.
1. Ajouter la nouvelle valeur à la fin du tableau.
2. Comparer la valeur à son parent.
3. Si l’ordre est violé, échanger l’enfant et le parent.
4. Répéter jusqu’à la racine ou jusqu’à ce que l’ordre soit respecté.
Insertion de 2 dans le tas minimum [3, 8, 5, 12, 10, 17, 9] Ajout en fin : [3, 8, 5, 12, 10, 17, 9, 2] 2 < 12 : échange -> [3, 8, 5, 2, 10, 17, 9, 12] 2 < 8 : échange -> [3, 2, 5, 8, 10, 17, 9, 12] 2 < 3 : échange -> [2, 3, 5, 8, 10, 17, 9, 12] |
Pseudo-code — Insérer dans un tas minimum Procedure InsererTasMin(T, n, valeur) T[n] <- valeur i <- n n <- n + 1 TantQue i > 0 Faire p <- (i - 1) div 2 Si T[p] <= T[i] Alors Quitter la boucle FinSi Echanger(T[p], T[i]) i <- p FinTantQue FinProcedure Dans une implémentation réelle, n est souvent transmis par référence ou géré par l’objet Tas. |
| Complexité — La nouvelle valeur remonte au plus sur la hauteur de l’arbre, soit O(log n). |
8.3.2 Remontée d’un élément
La remontée, aussi appelée tamisage vers le haut, montée ou sift-up, restaure la propriété d’ordre entre un nœud et ses ancêtres. Elle est utilisée après une insertion et après une modification rendant une clé plus prioritaire.
Pseudo-code — Remonter dans un tas minimum Procedure RemonterMin(T, i) TantQue i > 0 Faire p <- (i - 1) div 2 Si T[p] <= T[i] Alors Retourner Echanger(T[p], T[i]) i <- p FinTantQue FinProcedure |
Tas | Condition provoquant une remontée | Comparaison |
|---|---|---|
| Tas minimum | La nouvelle clé devient plus petite. | enfant < parent |
| Tas maximum | La nouvelle clé devient plus grande. | enfant > parent |
8.3.3 Extraction du minimum ou du maximum
L’élément prioritaire se trouve à la racine, donc à l’indice 0. Le supprimer directement laisserait un trou au début du tableau. Pour conserver la forme complète, la dernière valeur remplace la racine, la taille diminue, puis cette valeur descend jusqu’à retrouver une position valide.
1. Mémoriser la valeur de la racine.
2. Copier la dernière valeur à l’indice 0.
3. Diminuer le nombre d’éléments.
4. Faire descendre la nouvelle racine en choisissant l’enfant le plus prioritaire.
5. Retourner la valeur initialement mémorisée.
Extraction du minimum dans [2, 3, 5, 8, 10, 17, 9, 12] Minimum extrait : 2 Remplacement : [12, 3, 5, 8, 10, 17, 9] 12 > min(3, 5) : échange avec 3 -> [3, 12, 5, 8, 10, 17, 9] 12 > min(8,10) : échange avec 8 -> [3, 8, 5, 12, 10, 17, 9] |
Pseudo-code — Extraire le minimum Fonction ExtraireMinimum(T, n) : Valeur Si n = 0 Alors Erreur("Tas vide") minimum <- T[0] T[0] <- T[n - 1] n <- n - 1 DescendreMin(T, n, 0) Retourner minimum FinFonction |
| Complexité — L’accès au minimum est O(1), mais son extraction nécessite une descente en O(log n). |
8.3.4 Descente d’un élément
La descente, ou sift-down, compare un nœud à ses enfants. Dans un tas minimum, il faut sélectionner le plus petit enfant ; dans un tas maximum, le plus grand. Si cet enfant est plus prioritaire que le parent, ils sont échangés.
Pseudo-code — Descendre dans un tas minimum Procedure DescendreMin(T, n, i) TantQue VRAI Faire gauche <- 2 * i + 1 droite <- 2 * i + 2 plusPetit <- i Si gauche < n ET T[gauche] < T[plusPetit] Alors plusPetit <- gauche FinSi Si droite < n ET T[droite] < T[plusPetit] Alors plusPetit <- droite FinSi Si plusPetit = i Alors Retourner Echanger(T[i], T[plusPetit]) i <- plusPetit FinTantQue FinProcedure |
| Erreur fréquente — Dans un tas minimum, il faut comparer avec le plus petit des deux enfants. Échanger systématiquement avec l’enfant gauche peut laisser une violation du côté droit. |
8.3.5 Modifier une priorité
La modification d’une clé peut nécessiter une remontée ou une descente. Dans un tas minimum, diminuer une clé la rend plus prioritaire et impose une remontée ; l’augmenter peut imposer une descente.
Opération | Tas minimum | Tas maximum |
|---|---|---|
Diminuer une clé | Remontée possible | Descente possible |
Augmenter une clé | Descente possible | Remontée possible |
Pseudo-code — Diminuer une clé dans un tas minimum Procedure DiminuerCle(T, i, nouvelleCle) Si nouvelleCle > T[i] Alors Erreur("La nouvelle clé est plus grande") FinSi T[i] <- nouvelleCle RemonterMin(T, i) FinProcedure |
8.3.6 Construction d’un tas
Construire un tas par insertions successives est correct, mais coûte O(n log n). Une méthode plus efficace consiste à partir du dernier nœud interne et à appliquer une descente jusqu’à la racine. Les feuilles sont déjà des tas valides à un élément.
Construction bottom-up de [9, 4, 7, 1, 3, 6, 2] Tableau initial : [9, 4, 7, 1, 3, 6, 2] Dernier interne : indice (7 div 2) - 1 = 2 i = 2 : descente de 7 -> [9, 4, 2, 1, 3, 6, 7] i = 1 : descente de 4 -> [9, 1, 2, 4, 3, 6, 7] i = 0 : descente de 9 -> [1, 3, 2, 4, 9, 6, 7] |
Pseudo-code — Construire un tas minimum Procedure ConstruireTasMin(T, n) Pour i allant de (n div 2) - 1 à 0 avec un pas de -1 Faire DescendreMin(T, n, i) FinPour FinProcedure |
| Résultat important — La construction bottom-up d’un tas est en O(n), et non en O(n log n). Les nombreux nœuds proches des feuilles effectuent très peu de déplacements. |
8.3.7 Tableau récapitulatif des opérations
Opération | Tas binaire | Commentaire |
|---|---|---|
| Consulter minimum / maximum | O(1) | Valeur à la racine. |
| Insérer | O(log n) | Ajout en fin puis remontée. |
| Extraire l’élément prioritaire | O(log n) | Remplacement par le dernier puis descente. |
| Modifier une priorité | O(log n) | Remontée ou descente. |
| Construire un tas | O(n) | Construction bottom-up. |
| Rechercher une clé quelconque | O(n) | Absence d’ordre total. |
8.4 Files de priorité
8.4.1 Définition
Une file de priorité est un type abstrait de données dans lequel chaque élément possède une priorité. L’opération de retrait sélectionne l’élément le plus prioritaire, et non nécessairement le plus ancien.
Composante | Description |
|---|---|
| Élément | Objet ou donnée à traiter : tâche, patient, événement, paquet réseau, etc. |
| Priorité | Clé comparable déterminant l’ordre de traitement. |
| Convention min | La plus petite clé représente la priorité la plus forte. |
| Convention max | La plus grande clé représente la priorité la plus forte. |
| Règle d’égalité | Ordre d’arrivée, identifiant ou autre critère secondaire. |
8.4.2 Interface abstraite
Pseudo-code — Interface d’une file de priorité minimale TypeAbstrait FilePrioriteMin Creer() : FilePrioriteMin EstVide(F) : Booleen Taille(F) : Entier Inserer(F, element, priorite) ConsulterMinimum(F) : Element ExtraireMinimum(F) : Element ModifierPriorite(F, identifiant, nouvellePriorite) FinTypeAbstrait |
| Contrat — ConsulterMinimum et ExtraireMinimum exigent une file non vide. Une implémentation doit définir clairement le comportement en cas de structure vide. |
8.4.3 Insertion d’un élément prioritaire
L’élément et sa priorité peuvent être stockés dans un enregistrement. Le tas compare les priorités, mais l’extraction retourne l’élément complet.
Pseudo-code — Enregistrement prioritaire Type EntreePrioritaire element : Donnee priorite : Nombre ordreArrivee : Entier FinType |
L’ordre d’arrivée permet de rendre le traitement stable : à priorité égale, le premier arrivé est extrait en premier.
Pseudo-code — Comparaison stable Fonction PlusPrioritaire(a, b) : Booleen Si a.priorite < b.priorite Alors Retourner VRAI Si a.priorite > b.priorite Alors Retourner FAUX Retourner a.ordreArrivee < b.ordreArrivee FinFonction |
8.4.4 Extraction de l’élément prioritaire
L’extraction utilise l’opération du tas correspondant. Dans une file minimale, l’entrée de plus petite priorité numérique est retirée ; dans une file maximale, celle de plus grande priorité est retirée.
Pseudo-code — Extraire une entrée prioritaire Fonction ExtrairePrioritaire(F) : Element Si F.taille = 0 Alors Erreur("File vide") entree <- ExtraireMinimum(F.tas, F.taille) Retourner entree.element FinFonction |
8.4.5 Comparaison de plusieurs implémentations
Implémentation | Insertion | Consulter prioritaire | Extraction prioritaire | Usage |
|---|---|---|---|---|
Tableau non trié | O(1) | O(n) | O(n) | Beaucoup d’insertions, rares extractions. |
Tableau trié | O(n) | O(1) | O(1) | Peu d’insertions, nombreuses consultations. |
Liste non triée | O(1) | O(n) | O(n) | Implémentation simple et dynamique. |
Liste triée | O(n) | O(1) | O(1) | Petites structures. |
Tas binaire | O(log n) | O(1) | O(log n) | Compromis général efficace. |
| Choix usuel — Le tas binaire offre des performances équilibrées et prévisibles pour une file de priorité dynamique. |
Applications
Application 1 — Ordonnancement de tâches
Un ordonnanceur doit sélectionner la tâche ayant la plus forte priorité. Une file maximale convient si une valeur élevée signifie une priorité forte. Les tâches sont insérées au fur et à mesure de leur arrivée, puis extraites une par une pour être exécutées.
Tâche | Priorité | Durée estimée |
|---|---|---|
Compilation urgente | 9 | 4 min |
Sauvegarde | 4 | 10 min |
Mise à jour critique | 10 | 6 min |
Rapport quotidien | 3 | 2 min |
Pseudo-code — Ordonnanceur simple Procedure ExecuterTaches(listeTaches) F <- CreerFilePrioriteMax() Pour chaque tache dans listeTaches Faire Inserer(F, tache, tache.priorite) FinPour TantQue NON EstVide(F) Faire t <- ExtraireMaximum(F) Executer(t) FinTantQue FinProcedure |
| Attention — Un système réel doit éviter la famine des tâches de faible priorité, par exemple en augmentant progressivement leur priorité avec le temps. |
Application 2 — Gestion des urgences
Dans un service d’urgence, chaque patient reçoit un niveau de gravité. Le patient le plus grave doit être pris en charge en premier. En cas d’égalité, l’ordre d’arrivée peut départager les patients.
Patient | Gravité | Ordre d’arrivée | Ordre de prise en charge |
|---|---|---|---|
P1 | 3 | 1 | 3e |
P2 | 5 | 2 | 1er |
P3 | 4 | 3 | 2e |
P4 | 3 | 4 | 4e |
Une file maximale est naturelle si le niveau 5 est plus urgent que le niveau 1. L’enregistrement conserve aussi l’ordre d’arrivée pour stabiliser les égalités.
Application 3 — Simulation d’événements
Dans une simulation à événements discrets, chaque événement possède une date d’exécution. L’événement ayant la date la plus proche doit être traité en premier. Une file de priorité minimale est donc adaptée.
Pseudo-code — Boucle d’une simulation événementielle Procedure Simuler(F, tempsFin) tempsCourant <- 0 TantQue NON EstVide(F) Faire evenement <- ExtraireMinimum(F) Si evenement.date > tempsFin Alors Retourner tempsCourant <- evenement.date nouveaux <- Traiter(evenement, tempsCourant) Pour chaque e dans nouveaux Faire Inserer(F, e, e.date) FinPour FinTantQue FinProcedure |
Ce modèle est utilisé pour simuler une file d’attente, un réseau, une chaîne de production ou un système de réservation.
Application 4 — Tri par tas
Le tri par tas utilise un tas maximum pour produire un ordre croissant. Après la construction du tas, le maximum situé à la racine est échangé avec le dernier élément de la zone non triée. La taille logique du tas diminue, puis la racine descend.
Pseudo-code — Tri par tas croissant Procedure TriParTas(T, n) ConstruireTasMax(T, n) Pour fin allant de n - 1 à 1 avec un pas de -1 Faire Echanger(T[0], T[fin]) DescendreMax(T, fin, 0) FinPour FinProcedure |
Propriété | Tri par tas |
|---|---|
| Complexité temporelle | O(n log n) dans tous les cas |
| Mémoire auxiliaire | O(1) pour une version en place |
| Stabilité | Non stable dans sa forme classique |
| Données presque triées | Ne bénéficie pas particulièrement de l’ordre initial |
Travaux dirigés
TD 1 — Reconnaître un tas
Pour chacun des tableaux suivants, préciser s’il représente un tas minimum, un tas maximum, les deux ou aucun :
- A = [2, 5, 4, 9, 7, 8, 6] ;
- B = [12, 9, 10, 4, 8, 7, 6] ;
- C = [3, 6, 5, 2, 8] ;
- D = [5].
TD 2 — Calculer les relations d’indices
Dans un tas de 15 éléments indexés à partir de 0, déterminer pour les indices 0, 1, 4, 6, 7 et 14 : le parent, l’enfant gauche et l’enfant droit lorsqu’ils existent.
TD 3 — Tracer une insertion
Insérer successivement 6, 4, 8, 1, 3, 7 et 2 dans un tas minimum vide. Représenter le tableau après chaque insertion.
TD 4 — Tracer des extractions
À partir du tas minimum [1, 3, 2, 6, 4, 8, 7], effectuer deux extractions successives du minimum et donner chaque état intermédiaire.
TD 5 — Corriger un pseudo-code
Le pseudo-code suivant descend toujours vers l’enfant gauche. Expliquer l’erreur et proposer la correction.
Pseudo-code à corriger Procedure DescendreIncorrect(T, n, i) TantQue 2 * i + 1 < n Faire g <- 2 * i + 1 Si T[i] > T[g] Alors Echanger(T[i], T[g]) i <- g Sinon Retourner FinSi FinTantQue FinProcedure |
TD 6 — Construire un tas bottom-up
Transformer le tableau [14, 9, 3, 7, 5, 11, 2, 6] en tas minimum en appliquant les descentes du dernier nœud interne jusqu’à la racine.
TD 7 — Choisir une implémentation
Pour chaque situation, choisir entre tableau trié, tableau non trié et tas binaire, puis justifier :
- un million d’insertions suivies d’une seule extraction ;
- des insertions et extractions alternées en permanence ;
- une petite liste presque statique consultée très souvent ;
- une simulation générant continuellement de nouveaux événements.
TD 8 — Priorités égales
Proposer une clé composite garantissant qu’à priorité égale, les tâches sont traitées dans leur ordre d’arrivée. Donner la fonction de comparaison correspondante.
TD 9 — Analyse de complexité
Analyser le coût des opérations suivantes : construction par insertions successives, construction bottom-up, k extractions après construction et tri par tas.
TD 10 — Concevoir une file d’urgence
Définir les données, l’interface, la politique d’égalité et les jeux d’essai d’une file de patients prioritaire. Prévoir le changement du niveau de gravité d’un patient déjà enregistré.
Corrigés indicatifs des travaux dirigés
Correction du TD 1
Tableau | Résultat | Justification |
|---|---|---|
| A | Tas minimum | Chaque parent est inférieur ou égal à ses enfants. |
| B | Tas maximum | Chaque parent est supérieur ou égal à ses enfants. |
| C | Aucun | À l’indice 1, 6 > 2 : violation d’un tas minimum ; la racine 3 < 6 : violation d’un tas maximum. |
| D | Les deux | Un seul élément satisfait les deux propriétés. |
Correction du TD 2
i | Parent | Gauche | Droite |
|---|---|---|---|
0 | Aucun | 1 | 2 |
1 | 0 | 3 | 4 |
4 | 1 | 9 | 10 |
6 | 2 | 13 | 14 |
7 | 3 | Aucun | Aucun |
14 | 6 | Aucun | Aucun |
Correction du TD 3
Insertion | État du tas minimum |
|---|---|
6 | [6] |
4 | [4, 6] |
8 | [4, 6, 8] |
1 | [1, 4, 8, 6] |
3 | [1, 3, 8, 6, 4] |
7 | [1, 3, 7, 6, 4, 8] |
2 | [1, 3, 2, 6, 4, 8, 7] |
Correction du TD 4
Première extraction : le minimum 1 est retiré. Le dernier élément 7 remplace la racine, puis descend :
Première extraction [7, 3, 2, 6, 4, 8] -> échange avec 2 -> [2, 3, 7, 6, 4, 8] |
Deuxième extraction : le minimum 2 est retiré. Le dernier élément 8 remplace la racine :
Deuxième extraction [8, 3, 7, 6, 4] -> échange avec 3 -> [3, 8, 7, 6, 4] [3, 8, 7, 6, 4] -> échange avec 4 -> [3, 4, 7, 6, 8] |
Correction du TD 5
L’algorithme doit sélectionner l’enfant le plus petit. L’enfant droit peut être plus prioritaire que l’enfant gauche.
Pseudo-code corrigé Procedure DescendreMin(T, n, i) TantQue VRAI Faire g <- 2 * i + 1 d <- 2 * i + 2 m <- i Si g < n ET T[g] < T[m] Alors m <- g Si d < n ET T[d] < T[m] Alors m <- d Si m = i Alors Retourner Echanger(T[i], T[m]) i <- m FinTantQue FinProcedure |
Correction du TD 6
Construction bottom-up Initial : [14, 9, 3, 7, 5, 11, 2, 6] i = 3 : [14, 9, 3, 6, 5, 11, 2, 7] i = 2 : [14, 9, 2, 6, 5, 11, 3, 7] i = 1 : [14, 5, 2, 6, 9, 11, 3, 7] i = 0 : [2, 5, 3, 6, 9, 11, 14, 7] |
Correction du TD 7
Situation | Choix | Justification |
|---|---|---|
| Beaucoup d’insertions, une extraction | Tableau non trié | Insertion O(1), une seule recherche O(n). |
| Insertions et extractions alternées | Tas binaire | Deux opérations en O(log n). |
| Petite structure presque statique | Tableau trié | Consultation prioritaire O(1), coût d’insertion acceptable. |
| Simulation dynamique | Tas binaire | Événements ajoutés et extraits en continu. |
Correction du TD 8
Une clé composite peut être le couple (priorité, ordreArrivee). Pour une file minimale, on compare d’abord la priorité, puis l’ordre d’arrivée. Pour une file maximale, on peut comparer (-priorité, ordreArrivee) ou adapter la fonction de comparaison.
Correction du TD 9
Traitement | Complexité |
|---|---|
n insertions successives | O(n log n) |
Construction bottom-up | O(n) |
Construction puis k extractions | O(n + k log n) |
Tri par tas | O(n log n) |
Correction du TD 10
- Données : identifiant, nom, gravité, heure d’arrivée et informations médicales minimales.
- Clé : priorité décroissante sur la gravité, puis heure d’arrivée croissante.
- Opérations : enregistrer, consulter le prochain, extraire, modifier la gravité, annuler et rechercher par identifiant.
- Gestion des erreurs : patient absent, file vide, niveau de gravité invalide et identifiant dupliqué.
- Jeux d’essai : plusieurs gravités, égalités, modification d’une priorité, file vide et arrivées successives.
Travail pratique — Gestionnaire de tâches avec file de priorité
Objectif
Implémenter un gestionnaire de tâches reposant sur un tas maximum. Chaque tâche possède un identifiant, un libellé, une priorité, une durée estimée et un ordre d’arrivée.
Fonctionnalités demandées
1. Créer une file de priorité vide.
2. Ajouter une tâche.
3. Afficher la tâche la plus prioritaire sans la retirer.
4. Extraire et exécuter la tâche la plus prioritaire.
5. Modifier la priorité d’une tâche existante.
6. Annuler une tâche par identifiant.
7. Afficher toutes les tâches dans leur ordre interne de tas.
8. Exécuter toutes les tâches et produire un journal d’exécution.
Structure proposée
Pseudo-code — Structure Tâche Type Tache id : Chaine libelle : Chaine priorite : Entier duree : Entier ordreArrivee : Entier FinType |
Pseudo-code — Comparaison de deux tâches Fonction TachePlusPrioritaire(a, b) : Booleen Si a.priorite > b.priorite Alors Retourner VRAI Si a.priorite < b.priorite Alors Retourner FAUX Retourner a.ordreArrivee < b.ordreArrivee FinFonction |
Jeux d’essai minimaux
Cas | Données | Résultat attendu |
|---|---|---|
| File vide | Consulter / extraire | Erreur contrôlée. |
| Priorités différentes | T1:3, T2:8, T3:5 | T2, puis T3, puis T1. |
| Priorités égales | T1:5 arrivée 1, T2:5 arrivée 2 | T1 avant T2. |
| Augmentation | T1 passe de 3 à 9 | T1 remonte vers la racine. |
| Diminution | Racine passe de 9 à 2 | La tâche descend. |
| Annulation | Supprimer une tâche interne | Tas valide après réorganisation. |
Critères d’évaluation
Critère | Points |
|---|---|
Correction des opérations du tas | 6 |
Respect de la stabilité des priorités égales | 2 |
Gestion des erreurs et cas limites | 3 |
Qualité des jeux de tests | 3 |
Clarté et modularité du programme | 3 |
Analyse de complexité et documentation | 3 |
Extension facultative
- Appliquer un vieillissement : augmenter la priorité des tâches qui attendent trop longtemps.
- Associer une date limite à chaque tâche.
- Comparer expérimentalement le tas à un tableau trié et à un tableau non trié.
- Utiliser une table de hachage complémentaire pour retrouver rapidement l’indice d’une tâche par son identifiant.
Synthèse du chapitre
Notion | À retenir |
|---|---|
| Tas binaire | Arbre binaire complet respectant une propriété d’ordre locale. |
| Tas minimum | Chaque parent est inférieur ou égal à ses enfants ; la racine est minimale. |
| Tas maximum | Chaque parent est supérieur ou égal à ses enfants ; la racine est maximale. |
| Tableau | Représentation compacte avec calcul direct des indices. |
| Insertion | Ajout à la fin puis remontée en O(log n). |
| Extraction | Remplacement de la racine par le dernier puis descente en O(log n). |
| Construction | Méthode bottom-up en O(n). |
| File de priorité | Structure extrayant l’élément le plus prioritaire. |
| Tri par tas | Tri en place en O(n log n), généralement non stable. |
Glossaire
Terme | Définition |
|---|---|
| Tas | Arbre binaire complet doté d’une propriété d’ordre. |
| Heap | Terme anglais pour tas ; à ne pas confondre avec la zone mémoire dynamique. |
| Remontée | Déplacement d’un élément vers ses ancêtres après insertion ou changement de priorité. |
| Descente | Déplacement d’un élément vers ses descendants après extraction ou changement de priorité. |
| Heapify | Opération de restauration ou de construction de la propriété de tas. |
| File de priorité | TAD dans lequel le retrait dépend de la priorité. |
| Clé composite | Clé constituée de plusieurs critères, par exemple priorité puis ordre d’arrivée. |
| Tri par tas | Algorithme de tri utilisant un tas maximum ou minimum. |
Auto-évaluation
Je peux… | Oui | À revoir |
|---|---|---|
distinguer un tas minimum d’un tas maximum. | ☐ | ☐ |
vérifier la complétude et la propriété d’ordre. | ☐ | ☐ |
calculer les indices d’un parent et de ses enfants. | ☐ | ☐ |
tracer une insertion et une remontée. | ☐ | ☐ |
tracer une extraction et une descente. | ☐ | ☐ |
construire un tas bottom-up. | ☐ | ☐ |
analyser la complexité des opérations. | ☐ | ☐ |
concevoir une file de priorité stable. | ☐ | ☐ |
expliquer le principe du tri par tas. | ☐ | ☐ |
Conclusion
Le tas binaire fournit une réponse efficace aux problèmes où l’élément le plus prioritaire doit être consulté et extrait fréquemment. Sa représentation compacte, ses opérations logarithmiques et sa construction linéaire en font une structure essentielle. La compréhension des remontées, des descentes et de la relation entre arbre et tableau prépare directement l’étude du tri par tas, des files de priorité avancées et de nombreux algorithmes sur les graphes.