La représentation suivante des listes (entassées) vous mettra sur la piste de la définition d'un tas max.

1. Représentation de [89, 85, 86, 39, 77, 64, 58, 14] :
   
2. Représentation de [75, 69, 67, 63, 63, 57, 59, 53, 57] :
   
3. Représentation de [92, 79, 60, 32, 77, 53, 44, 26, 14, 58, 35, 18, 50, 10, 29] :
   

• Il s'agit d'un arbre binaire (chaque noeud a au plus deux fils : un fils gauche et un fils droit).
• Chaque niveau est complet, sauf peut-être le dernier. Si le dernier niveau n'est pas complet, les noeuds de ce niveau sont le plus à gauche possible.
• Chaque noeud contient une valeur au plus égale à celle de son parent.

La racine de l'arbre contient donc la plus grande des valeurs inscrites dans les noeuds.

A partir de l'arbre, on retrouve la liste (entassée) avec les relations suivantes :

• La racine de l'arbre est l'élément d'indice 0 dans la liste.
• Le fils droit de l'élément d'indice i dans la liste est l'élément d'indice 2i+1.
• Le fils gauche de l'élément d'indice i dans la liste est l'élément d'indice 2i+2.
• Le parent de l'élément d'indice i de la liste est \( \lceil \frac{i}{2}-1 \rceil\) (où \( \lceil \ \ \rceil\) est la fonction partie entière supérieure).
• On peut également ajouter que l'élément de la liste ayant pour indice len(liste)-1 (c'est à dire le dernier élément de la liste) est la feuille de l'arbre se trouvant au niveau le plus bas de l'arbre (où "bas" est relatif à la représentation classique plaçant la racine en haut !) et le plus à droite.

Le plus grand élément de la liste entassée se trouve à l'indice 0.

Pour construire l'arbre à partir de la liste entassée : on lit les éléments de la liste dans l'ordre des indices et on crée les noeuds de haut en bas et de gauche à droite au fur et à mesure de cette lecture de la liste.

Il nous restera bien sûr à déterminer comment l'on passe de la liste initiale à la liste entassée !

L'effet de entasser est le même que celui de heapq._heapify_max, il s'agit donc de la procédure de transformation de la liste en liste entassée.

On peut le constater avec quelques tests :

from random import randint
from copy import deepcopy
import heapq

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):
	g, d = gauche(i), droit(i)
	indice_max = len(liste)-1
	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)
	
	
def entasser(liste):
	for i in range(len(liste)//2, -1, -1):
		tamiser(liste, i)
		
		
		
L = [randint(10,99) for _ in range(randint(5,15))]
 
M = deepcopy(L)
entasser(L)
heapq._heapify_max(M)	
print(M == L)

Pour comprendre le fonctionnement de la fonction tamiser, on part de la liste L = [62, 79, 60, 32, 77, 53, 44, 26, 14, 58, 35, 18, 50, 10, 29] qui est presque un tas max : seule la racine ne respecte pas la contrainte de comparaison puisque cette racine est inférieure à au moins l'un de ses fils.

Regardons l'effet de la fonction tamiser sur cette liste.

On affiche les états intermédiaires avec ce code :

from math import ceil
from random import randint
from copy import deepcopy
import heapq

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 parent(i):
	""" indice dans la liste du parent
	de l'élément d'indice i."""
	return  ceil(i/2-1)
	
def tamiser(liste, i):
	g, d = gauche(i), droit(i)
	indice_max = len(liste)-1
	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]
		print(liste)
		tamiser(liste, indice_du_max)
	
	
L = [62, 79, 60, 32, 77, 53, 44, 26, 14, 58, 35, 18, 50, 10, 29]
print(L)
tamiser(L, 0)

On obtient :

 
[62, 79, 60, 32, 77, 53, 44, 26, 14, 58, 35, 18, 50, 10, 29]
[79, 62, 60, 32, 77, 53, 44, 26, 14, 58, 35, 18, 50, 10, 29]
[79, 77, 60, 32, 62, 53, 44, 26, 14, 58, 35, 18, 50, 10, 29]

La première transformation aboutit à cet arbre :

On a échangé la racine avec le plus grand de ses deux fils.

On constate alors qu'il n'y a plus de problème à la racine, mais le sous-arbre gauche

présente exactement le même problème que l'arbre initial. Il est donc naturel de tenter de le régler par le même processus, d'où l'appel récursif.

La seconde transformation aboutit à cet arbre :

On a à nouveau fait un échange entre le noeud posant problème et le plus grand de ses deux fils. On constate à ce stade que l'arbre est un tas-max.

Remarque : dans la littérature portant sur l'algorithmique, plutôt que de parler de tamis, on parle également souvent de percolation.

Pour comprendre que la fonction entasser transforme bien la liste en tas-max, il faut déjà remarquer qu'un arbre constitué d'un seul sommet est nécessairement un tas-max.

Pour un indice i de la liste L tel que \( 2i+1 > \text{len(L)}-1 \), c'est à dire tel que \( 2i > \text{len(L)}-2 \) ou encore \( i > \lfloor \frac{\text{len(L)}}{2} \rfloor -1 \), le noeud est une feuille (puisque ses éventuels fils ont pour indice 2i+1, 2i+2 qui sont au-delà des indices possibles).
Les noeuds d'indice \(\lfloor \frac{\text{len(L)}}{2} \rfloor, \lfloor \frac{\text{len(L)}}{2} \rfloor +1, \dots, \text{len(L)} -1 \) peuvent donc être considérés comme des tas-max (arbres avec comme seul sommet la racine).

On entasse alors petit à petit en tamisant les parents de ses noeuds un à un. Au final, on obtient bien un tas-max.