Illustrons le principe via un exemple.

On veut trier la liste L = [63, 69, 67, 57, 63, 57, 59, 53, 75].

1. On commence par entasser la liste à trier. On obtient : L = [75, 69, 67, 63, 63, 57, 59, 53, 57], soit
   
2. L'élément L[0] est le plus grand élément de la liste. On l'échange avec le dernier. On obtient : L = [57, 69, 67, 63, 63, 57, 59, 53, 75], soit
   
3. On "sort" le dernier élément du tas : ce dernier élément est à sa place définitive, on n'y touchera plus.
   L'arbre restant par contre ne vérifie plus la structure de tas-max, il nous faut tamiser l'élément de tête, mais attention, cela doit être fait sur la sous-liste [L[0], L[1], ..., L[len(L)-2] ], sinon notre liste se retrouve dans l'état entassé de départ. Pour cela, on pourra modifier la fonction tamiser en faisant en sorte que la variable indice_max devienne un paramètre.
   Après ce tassage, la liste devient :
   
4. On échange alors la racine du tas-max avec le dernier élément du tas-max. La liste devient [53, 63, 67, 57, 63, 57, 59] + [69, 75], soit :
   
   On tamise :
   
5. und so weiter...

Les états de la liste sont donc :

• Avant le tri : [63, 69, 67, 57, 63, 57, 59, 53, 75]
  Après tassage : [75, 69, 67, 63, 63, 57, 59, 53, 57]
• Liste après échange de la tête du tas et de sa queue : [57, 69, 67, 63, 63, 57, 59, 53, 75] []
  Liste après tamisage de la nouvelle tête : [69, 63, 67, 57, 63, 57, 59, 53] [75]
• Liste après échange de la tête du tas et de sa queue : [53, 63, 67, 57, 63, 57, 59, 69] [75]
  Liste après tamisage de la nouvelle tête : [67, 63, 59, 57, 63, 57, 53] [69, 75]
• Liste après échange de la tête du tas et de sa queue : [53, 63, 59, 57, 63, 57, 67] [69, 75]
  Liste après tamisage de la nouvelle tête : [63, 63, 59, 57, 53, 57] [67, 69, 75]
• Liste après échange de la tête du tas et de sa queue : [57, 63, 59, 57, 53, 63] [67, 69, 75]
  Liste après tamisage de la nouvelle tête : [63, 57, 59, 57, 53] [63, 67, 69, 75]
• Liste après échange de la tête du tas et de sa queue : [53, 57, 59, 57, 63] [63, 67, 69, 75]
  Liste après tamisage de la nouvelle tête : [59, 57, 53, 57] [63, 63, 67, 69, 75]
• Liste après échange de la tête du tas et de sa queue : [57, 57, 53, 59] [63, 63, 67, 69, 75]
  Liste après tamisage de la nouvelle tête : [57, 57, 53] [59, 63, 63, 67, 69, 75]
• Liste après échange de la tête du tas et de sa queue : [53, 57, 57] [59, 63, 63, 67, 69, 75]
  Liste après tamisage de la nouvelle tête : [57, 53] [57, 59, 63, 63, 67, 69, 75]
• Liste après échange de la tête du tas et de sa queue : [53, 57] [57, 59, 63, 63, 67, 69, 75]
  Liste après tamisage de la nouvelle tête : [53] [57, 57, 59, 63, 63, 67, 69, 75]
• Après le tri : [53, 57, 57, 59, 63, 63, 67, 69, 75]

from random import randint


def gauche(i): 
	""" indice dans la liste du fils gauche
	de l'élément d'indice i."""
	return 2*i+1
	
def droit(i):
	""" indice dans la liste du fils droit
	de l'élément d'indice i."""
	return 2*i+2
	
 
	
def tamiser(liste, i, indice_max):
	g, d = gauche(i), droit(i)
	if g <= indice_max and liste[g] > liste[i] :
		indice_du_max = g
	else :
		indice_du_max = i
	if d <= indice_max and liste[d] > liste[indice_du_max] :
		indice_du_max = d
	if indice_du_max != i :
		liste[i], liste[indice_du_max] = liste[indice_du_max], liste[i]
		tamiser(liste, indice_du_max, indice_max)
	
	
def entasser(liste):
	for i in range(len(liste)//2, -1, -1):
		tamiser(liste, i, len(liste)-1)

 

def heapsort(liste):
	indice_max = len(liste)-1 
	entasser(liste)
	for i in range(len(liste)-1, 0, -1) :
		liste[0], liste[i] = liste[i], liste[0]
		print("Liste après échange de la tête du tas et de sa queue : ")
		print(liste[0:i+1], end="    ")
		print(liste[i+1:])
		indice_max -= 1
		tamiser(liste, 0, indice_max)
		print("Liste après tamisage de la nouvelle tête : ")
		print(liste[0:i], end="    ")
		print(liste[i:])
		print()


L = [randint(10,99) for _ in range(randint(5,15))]
print("Avant le tri : ", L)
entasser(L)
print("Après tassage : ", L)
print()
heapsort(L)
print()
print("Après le tri : ", L)

On obtient par exemple :

 
Avant le tri :  [12, 24, 95, 38, 57, 99, 69]
Après tassage :  [99, 57, 95, 38, 24, 12, 69]

Liste après échange de la tête du tas et de sa queue : 
[69, 57, 95, 38, 24, 12, 99]    []
Liste après tamisage de la nouvelle tête : 
[95, 57, 69, 38, 24, 12]    [99]

Liste après échange de la tête du tas et de sa queue : 
[12, 57, 69, 38, 24, 95]    [99]
Liste après tamisage de la nouvelle tête : 
[69, 57, 12, 38, 24]    [95, 99]

Liste après échange de la tête du tas et de sa queue : 
[24, 57, 12, 38, 69]    [95, 99]
Liste après tamisage de la nouvelle tête : 
[57, 38, 12, 24]    [69, 95, 99]

Liste après échange de la tête du tas et de sa queue : 
[24, 38, 12, 57]    [69, 95, 99]
Liste après tamisage de la nouvelle tête : 
[38, 24, 12]    [57, 69, 95, 99]

Liste après échange de la tête du tas et de sa queue : 
[12, 24, 38]    [57, 69, 95, 99]
Liste après tamisage de la nouvelle tête : 
[24, 12]    [38, 57, 69, 95, 99]

Liste après échange de la tête du tas et de sa queue : 
[12, 24]    [38, 57, 69, 95, 99]
Liste après tamisage de la nouvelle tête : 
[12]    [24, 38, 57, 69, 95, 99]


Après le tri :  [12, 24, 38, 57, 69, 95, 99]