UE- PYTHON ET STRUCTURES DE DONNÉES AVANCÉES

Chapitre I : Listes chainées, Piles, Files

Chapitre II : Arbres
Chapitre III : Tas
III.1 Notion de tas
III.2 Conservation de la structure de tas
III.3 Construction d’un tas
III.4 Algorithme de tri par tas
III.5 Files de priorité

Durée : 4H ( CM :1H30, TD :1H, TP :1H30)

92
www.kadjo-lambert.c4.fr
Chapitre III : Tas
III.1 Notion de tas

Définition et caractéristiques
 Un tas (ou monceau) est un arbre binaire partiellement complet (arbre parfait)
étiquetté par des objets comparables tel que
tout nœud interne possède une clé supérieure ou égale aux clés de ses fils
pour un tas max (binary maxheap)
tout nœud interne possède une clé inférieure ou égale aux clés de ses fils pour
un tas min (binary minheap)
NB: Généralement, le tas max est appelé simplement tas
On a donc la propriété suivante pour les tas :
 Pour tous les nœuds de l'arbre autre que la racine,
étiquette(père) ≥ étiquette(fils).
 La hauteur d'un tas est O(lg n)

 Un tas est une structure de données qui

◦ Permet un nouveau type de tri (Tri par tas)
◦ Permet l'implémentation de files de priorité
 NB: Le fait qu'un tas soit un arbre binaire complet permet de le représenter
d'une manière efficace par un tableau unidimensionnel. 93
Chapitre III : Tas
III.1 Notion de tas

Représentation par tableaux

Un tas peut être représenté par un tableau T indicé à partir de 1, avec un accès en O(1) à
chaque nœud:
 On numérote les sommets par un parcours en largeur, de gauche à droite
(Mémorisation des nœuds séquentiellement de la racine aux feuilles et de gauche vers
1
la droite).
 Fils gauche de T[i] est en T[2i] 18
 Fils droit de T[i] est en T[2i + 1]
 Père de T[i] est en T[i/2] 2 3
15 16
4 5 6 7
Si on traduit cette propriété sur la représentation T[1..n], 14 13 10 8
on obtient : 9 10
T[i]  T [2i] et T[i]  T[2i + 1], pour i  1, 2i + 1  n 8 7 11
9 11 12
Ou
T[i]  T [2i], i  1, 2i  n
T [1]  T [i], i  n
tab T: 18 15 16 14 13 10 8 7 9 11 12
1 2 3 4 5 6 7 8 9 10 11 94
Chapitre III : Tas
III.1 Notion de tas

Quelques procédures
– La procédure Percoler() qui s’exécute en O(lg n), permet de la conservation de la propriété
de tas max. Si la valeur du nœud est augmentée et qu'elle devient de ce fait supérieure à
celle de son père, il suffit de l'échanger avec celle-ci, puis de continuer ce processus vers le
haut jusqu'au rétablissement de la propriété du tas. On dit que la valeur modifiée a été
percolée jusqu'à sa nouvelle position,

– La procédure ConstruireTasMAX(), qui s’exécute en un temps linéaire, produit un tas max

à partir d’un tableau d’entrée non-ordonné.
– La procédure Tamiser() ou Entasser, recevant pour paramètres un tas T et un nœud i
replacer la valeur en i pour conserver la structure de tas,

– Les procédures InsereTasMAX(), ExtraireMAXdeTAS(), AugmenterCleTAS() et

MaxmumTAS(), qui s’exécutent en O(lg n), permettent d’utiliser la structure de données de
tas pour gérer une file de priorité

95
Chapitre III : Tas
III.2 Conservation de la structure de tas

Modification de la clé d’un noeud

PROCEDURE Percoler(T[0..n-1], i)
Données : tableau T, nœud i
Résultat : T est de nouveau un tas
Début
ki
REPETER
jk
SI j > 1 ET T[j div 2] < T[k] ALORS
k  j div 2
echanger T[j] et T[k]
FinSI 1
JUSQU'A j = k 18
FinProcédure
2 3
15 16
4 5 6 7
14 13 10 8
8 9 10 11
7 9 17 12 96
Chapitre III : Tas
III.2 Conservation de la structure de tas

Modification de la clé d’un noeud

 Entrée : soient un tableau T et un indice i
si la valeur du nœud i est diminuée et qu'elle devient de ce fait inférieure à celle d'au moins
un de ses fils, il suffit de l'échanger avec la plus grande des valeurs de ses fils, puis de
continuer ce processus vers le bas jusqu'au rétablissement de la propriété du tas. On dit que
la valeur modifiée a été tamisée jusqu'à sa nouvelle position (entasser).

 Condition :
 les arbres binaires Gauche(i) et Droite(i) sont des tas max
A[i] peut être plus petit que ses enfants (et donc un tri est nécessaire)
La procédure EntasserMax va faire évoluer l'arbre afin d'obtenir un tas max en i
1
18

2 3
11 16
4 5 6 7
14 15 10 8
8 9 10 11
7 9 13 12 97
Chapitre III : Tas
III.2 Conservation de la structure de tas

Modification de la clé d’un noeud

Fonction PARENT(i)
retourner i/2
Procédure EntasserMAX(T,i)
Fonction GAUCHE(i) Données : tableau T, nœud i
retourner 2i Résultat : T est de nouveau un tas

Fonction DROITE(i) Debut

retourner 2i + 1 l  Gauche(i)
r  Droite(i)
si l ≤ taille(T) et T[l] > T[i] Alors
max  l
sinon max  i
FinSi
si r ≤ taille(T) et T[r] > T[max] alors
max  r
FinSi
si max ≠ i Alors
Permute (T[i], T[max])
EntasserMAX(T,max)
FinSi
FIN 98
Chapitre III : Tas
III.3 Construction d’un tas

Procédure ConstruireTasMAX version1

On va effectuer un parcours ascendant par niveau et transformer si nécessaire les sous
arbres rencontrés pour qu’ils vérifient la propriété du TAS.

Procédure ConstruireTasMAX (T[1..n] )

i : entier
Début
i  n div 2 1
Tant que i  1 faire 8
EntasserMAX(T,i])
i i–1 2 3
Fin Tant que 10 16
Fin ;
4 5 6 7
15 14 9 18
8 9 10 11
7 13 12 11 99
Chapitre III : Tas
III.3 Construction d’un tas

Procédure ConstruireTasMAX version2

Procedure TransformeEnTasMAX (T[i..n] )

FilsMax : entier
Début
FilsMax  2i # indice fils gauche, s’il existe
Si FilsMax  n alors # il y a au moins un sous arbre
Si FilsMax < n alors # il y a 2 sous-arbres
Si T [FilsMax + 1] > T[FilsMax] alors
FilsMax  FilsMax + 1
FinSi
#FilsMax désigne le plus grand des 2 fils
Fin Si
Si T[FilsMax] > T[i] alors
Permute (T[FilsMax], T[i])
TransformeEnTasMax (T[FilsMax..n])
Fin Si
Fin Si
100
Fin
Chapitre III : Tas
III.3 Construction d’un tas

Procédure ConstruireTasMAX version2

On va effectuer un parcours ascendant par niveau et transformer si nécessaire les sous
arbres rencontrés pour qu’ils vérifient la propriété du TAS.

Procédure ConstruireTasMAX (T[1..n] )

i : entier
Début
i  n div 2
Tant que i  1 faire
TransformeEnTasMAX (T[i..n])
i i–1
Fin Tant que
Fin ;

101
Chapitre III : Tas
III.3 Construction d’un tas

Exemple

E3 30
7
7

30 0 15
20
E1
E4
0 30 15 20 -2 4
7 Ok2
E2
15 0 Ok3
Ok1

102
Chapitre III : Tas
III.4 Algorithme de tri par tas

Algorithme
Procedure TrisTAS T([1..n] )
Nb : entier
Début
ConstruireTaxMAX (T[1..n])
Permute (t[1], T[n])
Nb  n – 1
Tant que Nb > 1 faire
TransformeEnTasMAX (T[1..Nb])
Permute (T[1], T [Nb])
Nb  Nb – 1
Fin Tant que
Fin ;

103
Chapitre III : Tas
III.5 Files de priorité

Définition et caractéristiques
Structure de données permettant de gérer un ensemble S d'éléments auxquels on associe
une "clé"
Cette clé permet la définition des priorités

Application directe de la structure de tas

4 opérations (File-Max)
 MaximumTAS(T)
ExtraireMaxTAS(T)
AugmenterCleTAS(T,x,k)
Insérer(T,x)
Si on inverse l'ordre des priorités (File-Min), on obtient les opérations
symétriques (Minimum, Extraire-Min, Diminuer-Clé)
Utilisation :
Cas d'une liste de tâches sur un ordinateur

La file de priorité gère les tâches en attente selon leur priorité
Quand une tâche est terminée, on exécute la tâche de priorité la plus élevée suivante
Il est possible d'insérer dans la file une tâche, éventuellement prioritaire
104
Chapitre III : Tas
III.5 Files de priorité

Procédures et fonctions
 Retourner l'élément ayant la clé maximale

Fonction MaximumTAS T([1..n] )

Début
Retourner (T[1])
Fin

Retourner l'élément ayant la clé maximale en le supprimant de la file

Fonction ExtraireMaxTAS (T[1..n] )

max : entier
Début
max  T[1]
T[1]  T[taille[T]]
taille[T]  taille[T]-1
EntasserMax(T,1)
Retourner(max)
Fin 105
Chapitre III : Tas
III.5 Files de priorité

Procédures et fonctions
 Insérer un élément dans un Tas
 Augmenter la valeur d'une clé
Procedure InsererTasMAX(T, clé )
Début
taille[T]  taille[T]+1
Procedure AugmenterCleTAS (T,i,clé )
T[taille[T] ]  clé
Début
AugmenterCleTAS (T, taille[T] ,clé )
Si clé < T[i]
Fin
alors ERREUR
sinon
T[i]  clé
TantQue i> 1 et T[Parent(i)]<T[i] faire
permute(T[i], T[Parent(i)])
i T[Parent(i)]
Fin Tanque
FinSI
Fin

106