Cette méthode de tri (aussi appelée «tri par tas» ou «heapsort» ou «tri de Williams») est basée sur la notion de tas. Un tas est un arbre binaire parfait tel que l’information contenue dans tout nœud est supérieure à celle contenue dans ses fils. La méthode du tri par tas comporte deux étapes :
Construction par insertions successives d’un tas à partir du vecteur à trier.
On remplace la racine, qui est nécessairement le plus grand élément du tableau par son fils le plus grand. La racine est transférée à la place de la dernière feuille de l’arbre et celle-ci est repositionnée. On réitère avec la nouvelle racine autant de fois qu’il y a de nœuds dans l’arbre.
La démo ci-après illustre le fonctionnement de ce tri :
La complexité dans le pire des cas du tri maximier est en log2(n).