Prépa Code Connexion Inscription

Ecrire une fonction tri_par_tas(lst) qui renvoie une nouvelle liste contenant les elements de lst tries par ordre croissant, en utilisant l'algorithme du tri par tas (heapsort).

L'idee : 1. Construire un tas-max a partir de la liste (in-place). 2. Echanger la racine (le max) avec le dernier element, reduire la taille consideree du tas, puis retablir la propriete de tas. 3. Repeter jusqu'a ce que le tas soit vide.

Contraintes : ne pas utiliser sorted, list.sort ni le module heapq. La liste originale ne doit pas etre modifiee (vous pouvez en faire une copie).