Overview
Heap Sort construit un max-heap puis place le plus grand element a la fin a chaque tour.
Analogy
Comme une file de priorite: on prend toujours la valeur la plus grande en premier.
Step-by-step
- Transformer le tableau en max-heap (heapify).
- Echanger la racine avec la derniere case non triee.
- Reduire la taille du heap de 1.
- Faire sift-down depuis la racine.
- Repeter jusqu a taille 1.
Visual
[heap | sorted tail] : la partie triee grandit a droite.
Common mistakes
- Confondre index enfants en base 0 et base 1.
- Oublier de reduire heap_size apres chaque extraction.
- Utiliser sift-up au lieu de sift-down apres swap.
Practice questions
- Heapify [4,10,3,5,1] pas a pas.
- Expliquer pourquoi Heap Sort n est pas stable.
- Adapter en min-heap pour tri descendant.