How it works?

Un tas binaire réside dans un simple tableau. Pour le nœud à l'index i (basé sur 0), ses enfants se trouvent à 2*i + 1 et 2*i + 2. Cet indexage est toute l'astuce qui permet à un arbre de résider dans un tableau.

Processus étape par étape :

1. Construire un tas-max (max-heap) : réorganiser le tableau pour que chaque parent soit >= à ses enfants. La plus grande valeur se retrouve à l'index 0.
2. Extraire le maximum : échanger la racine (le plus grand) avec le dernier élément du tas, puis réduire la taille du tas de un afin que le plus grand soit désormais placé à la fin dans sa position triée finale.
3. Réparer avec un tamisage vers le bas (sift-down) : la nouvelle racine peut être mal placée, donc tamisez-la vers le bas (échangez-la avec son enfant le plus grand, répétez) jusqu'à ce que la propriété du tas soit à nouveau respectée.
4. Répéter jusqu'à ce que le tas soit vide. Le tableau est maintenant trié par ordre croissant.

Exemple sur [4, 10, 3, 5, 1] :

• Construire un tas-max : [10, 5, 3, 4, 1].
• Échanger la racine 10 vers la fin et tamiser vers le bas, puis répéter pour 5, 4, 3.
• Résultat : [1, 3, 4, 5, 10].