Le cours
Résumé en cinq points
- Une file de priorité offre insertion et extraction du minimum. Le tas réalise ces deux opérations en , contre un coût linéaire pour l'une des deux dans les implémentations naïves.
- Un tas min est un arbre binaire presque complet où chaque nœud est plus prioritaire que ses fils. Stocké dans un tableau, le nœud a ses fils en et et son père en .
- L'insertion percole vers le haut depuis la dernière case, l'extraction place le dernier élément à la racine et percole vers le bas en échangeant avec le fils le plus prioritaire.
- Un tas se construit en temps linéaire. Le tri par tas est en dans le pire des cas, en place, non stable.
- Avec un tas, Dijkstra passe de à , avantageux pour les graphes creux, et Kruskal peut remplacer le tri initial des arêtes par des extractions successives.
Pourquoi ce chapitre
Beaucoup d'algorithmes répètent la même opération : retirer d'une collection l'élément le plus urgent, puis en ajouter de nouveaux.
- Le plus proche sommet non encore traité chez Dijkstra.
- L'arête de plus petit poids chez Kruskal.
- La tâche la plus prioritaire dans un ordonnanceur.
PropriétéCompromis du tas
Une liste triée rend l'extraction rapide mais l'insertion lente, une liste non triée l'inverse. Le tas réalise le compromis, les deux opérations en temps logarithmique.
RemarqueReprésentation et applications
C'est aussi le premier exemple, au programme, d'un arbre qui n'est pas stocké avec des pointeurs mais dans un simple tableau, ce qui montre que l'arbre est d'abord une façon de penser une structure.
Aux concours, le tas intervient dans :
- l'implémentation des opérations ;
- la preuve de l'invariant ;
- l'analyse de complexité ;
- le tri par tas ;
- l'application à un algorithme de graphe.
Fin de l'aperçu gratuit
Encore 13 parties de cours et 8 corrigés.
Méthodes et exercices
Exercices classiques corrigés
Rangés par thème, du plus simple au plus exigeant. Difficulté et durée indicatives.
Opérations sur un tas 1
Exercice 1 ★
Application du cours · 15 min · Khôlle
Vérifier que t = [|2; 5; 3; 9; 6; 8; 4|] est un tas min. Y insérer 1, puis extraire le minimum. Donner l'état du tableau après chaque opération.
Voir l'indice
Technique percolations à la main, indices de la fiche.
Voir le corrigé offert
- Les nœuds internes sont 0, 1 et 2. On vérifie 2 ≤ 5 et 2 ≤ 3, puis 5 ≤ 9 et 5 ≤ 6, puis 3 ≤ 8 et 3 ≤ 4. C'est un tas.
- Insertion de 1 en case 7. Père 3 (valeur 9) : échange. Père 1 (valeur 5) : échange. Père 0 (valeur 2) : échange. Tableau
[|1; 2; 3; 5; 6; 8; 4; 9|], trois échanges, la hauteur ⌊log₂ 8⌋. - Extraction : on renvoie 1, on met 9 à la racine, taille 7. Fils 2 et 3 : échange avec 2. En case 1, fils 5 et 6 : échange avec 5. En case 3, aucun fils. Tableau
[|2; 5; 3; 9; 6; 8; 4|].
piège : En descendant, échanger avec le fils gauche par réflexe. En case 0, cela marche ici, mais avec des fils 3 et 2 on placerait 3 au-dessus de 2.
Construction d'un tas 2
Exercice 2. Construction d'un tas ★
Application du cours · 10 min · Khôlle
Appliquer construire à [|5; 3; 8; 1; 9; 2|] et compter les échanges.
Voir le début du corrigé
- n = 6, on traite i = 2, 1, 0.
La suite du corrigé dans Sup et Spé+ : essai gratuit 7 jours.
Exercice 9 ★★★
Approfondissement · 35 min · Écrit, type X ou ENS
Montrer que construire est en O(n) en calculant Σk≥0 k / 2k+1, puis montrer que les insertions successives de n, n − 1, …, 1 dans un tas min vide coûtent un nombre d'échanges de l'ordre de n log n.
Voir le début du corrigé
- Pour |x| < 1, Σ k xk−1 = 1/(1 − x)². …
La suite du corrigé dans Sup et Spé+ : essai gratuit 7 jours.
Propriétés du tas 1
Exercice 3 ★★
Classiques de khôlle et concours · 15 min · Khôlle
Dans un tas min de n éléments distincts, où peut se trouver le deuxième plus petit ? Le k-ième plus petit ? Où se trouve le plus grand ?
Voir le début du corrigé
- Le deuxième plus petit a tous ses ancêtres plus petits que lui, donc son seul ancêtre est la racine. …
La suite du corrigé dans Sup et Spé+ : essai gratuit 7 jours.
Tas comme file de priorité 2
Exercice 4 ★★
Classiques de khôlle et concours · 25 min · Écrit, type CCINP MP
Écrire une fonction qui renvoie, dans l'ordre croissant, les k plus petits éléments d'un tableau d'entiers t de taille n, avec 0 ≤ k ≤ n, en O(n + k log n). Le tableau t ne doit pas être modifié.
Voir le début du corrigé
- Idée : on copie t dans un tas de couples (x, x), on le construit en O(n), puis on extrait k fois en O(log n) chacune.
La suite du corrigé dans Sup et Spé+ : essai gratuit 7 jours.
Exercice 6 ★★
Classiques de khôlle et concours · 25 min · Écrit, type Mines
Fusionner k listes triées par ordre croissant, de longueur totale N, en une seule liste triée, en O(N log k).
Voir le début du corrigé
- Idée : le tas contient, pour chaque liste non vide, le couple (tête, reste). …
La suite du corrigé dans Sup et Spé+ : essai gratuit 7 jours.
Tri par tas 1
Exercice 5 ★★
Classiques de khôlle et concours · 15 min · Khôlle
Montrer sur un exemple que le tri par tas n'est pas stable. On trie [|(2, a); (2, b); (1, c)|] par clé croissante avec le tri par tas de la fiche, dans la variante de descendre_max qui compare les seules clés (fst).
Voir le début du corrigé
- Construction, n = 3, i = 0 : fils de clés 2 et 1, aucun n'est strictement plus grand que la racine de clé 2. …
La suite du corrigé dans Sup et Spé+ : essai gratuit 7 jours.
Dijkstra avec tas 2
Exercice 8 ★
Application du cours · 15 min · Écrit, type Centrale
Un graphe a n = 10⁴ sommets. Comparer l'ordre de grandeur du coût de Dijkstra naïf et avec tas pour m = 3 × 10⁴ (réseau routier), puis pour m = 5 × 10⁷ (graphe dense). Conclure.
Voir le début du corrigé
- Naïf : n² = 10⁸ dans les deux cas, m étant négligeable ou du même ordre.
La suite du corrigé dans Sup et Spé+ : essai gratuit 7 jours.
Exercice 7 ★★
Classiques de khôlle et concours · 20 min · Khôlle
Dérouler Dijkstra avec tas, depuis le sommet 0, sur le graphe à 4 sommets et 5 arcs : 0 → 1 (poids 4), 0 → 2 (1), 2 → 1 (2), 1 → 3 (1), 2 → 3 (5). Repérer les entrées périmées.
Voir le début du corrigé
- Insertion de (0, 0). Extraction (0, 0) : 0 traité, dist.(1) = 4 et dist.(2) = 1, insertions de (4, 1) et (1, 2).
La suite du corrigé dans Sup et Spé+ : essai gratuit 7 jours.
Fiche de cours rédigée à partir du programme officiel de l'option informatique de la filière MPSI-MP (2021), programme de deuxième année, partie 2.1 « Applications des arbres », point « File de priorité ».