Tri par Tas (Heap Sort)
Structure de tas et tri en place en O(n log n)
Enonce
Implémenter le tri par tas. La fonction modifie T en place et le retourne.
⚠ Contrainte : complexité $O(n\log n)$ en pire cas, $O(1)$ espace auxiliaire (tri en place).
Signature attendue
def tri_par_tas(T: list) -> list:Exemples
tri_par_tas([4, 10, 3, 5, 1])→[1, 3, 4, 5, 10]tri_par_tas([7, 7, 7])→[7, 7, 7]tri_par_tas([])→[]
📖 Rappel de cours
Un tas binaire max est un arbre binaire quasi-complet où chaque nœud est $\geq$ à ses enfants. On le stocke dans un tableau, sans pointeurs :
Représentation tableau :
Pour un nœud d'indice $i$ :
- parent = $\lfloor (i-1)/2 \rfloor$
- fils gauche = $2i + 1$
- fils droit = $2i + 2$
Algorithme heap sort :
- Construire le tas max (en place) : O(n)
- $n$ fois : échanger la racine (max) avec le dernier, réduire la taille, sift_down(0)
Complexité $O(n\log n)$ pire cas, tri en place ($O(1)$ espace auxiliaire) — contrairement au tri fusion.
← Exercices d'algorithmique en Python — tris, dichotomie, récursivité
Exercices du meme theme
- Détection de Cycle (Floyd)
- Arbres Binaires — Parcours et Hauteur
- Arbre Binaire de Recherche (ABR)
- Algorithme de Kadane
- Chemins dans une Grille
- Distance d'Édition (Levenshtein)
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.