Définition 5.1 Un tas max (resp.tas min) T est un arbre binaire quasi-parfait étiquetté par des objets comparables (ie : il existe un ordre total) tel que tout noeud a une étiquette plus grande (resp. plus petite) que ces fils.
Propriété 5.2 La hauteur d'un tas est O(log(n)).Un tas est un containeur et un arbre binaire, il dispose donc des primitives des arbres binaires ainsi que ceux d'un containeur :
fonction valeur(ref T:tas d'objet): objet;
// renvoit l'objet stocké à la racine de l'arbre
fonction ajouter(ref T:tas de objet,
val v:objet):vide;
// ajoute l'objet dans le tas
fonction supprimer(val T:tas de objet):vide;
// suppression de la racine et tassement de l'arbre
fonction creerTas(ref T:tas,val:v:objet):vide;
fonction detruireTas(ref T:tas):vide;
fonction tableauTas(ref L:liste d'entier):tas d'entier;
var T:tas d'entier;
début
premier(L);
creerTas(T,valeur(L));
suivant(L);
tantque valeur(L)!=NULL faire
ajouter(T,valeur(L));
suivant(L);
fintantque
retourner(T)
fin
Propriété 5.3 Si n est le nombre de sommets du tas, on obtient la liste triée en O(n log(n)).
fonction listeTas(val T:tas d'entier):liste de entier;
var L: listeSC de entier;
var r:entier;
début
creerListe(L);
tantque !estFeuille(T) faire
r= valeur(T);
supprimer(T);
insérerEnTete(L,r);
fintantque
insérerEnTete(L,valeur(T));
detruireTas(T);
retourner(L);
fin
Propriété 5.4. Le tri qui consiste àa une complexité O(n log(n)).
- Construire un tas
- Extraire la liste triée
tas=structure
arbre:tableau[1..tailleStock] d'objet;
tailleTas:entier;
finstructure;
curseur=entier;
sommet=entier;
De ce fait, les primitives arbre binaire prennent comme
paramètre un tas et non un sommet. On a
sommet=entier;Les fonction ajouter et supprimer sont spécifiques au tas.
fonction getValeur(ref T:tas d'objet;val s:sommet):objet;
début
retourner(T.arbre[s]);
fin;
fonction valeur(ref T:tas d'objet):objet;
début
retourner(T.arbre[1]);
fin
fonction filsGauche(val s:sommet):sommet;
début
retourner(2*s);
fin
fonction filsDroit(val s:sommet):sommet;
début
retourner(2*s+1);
fin
fonction pere(val s:sommet):sommet;
début
retourner(partieEntiere(s/2));
fin
fonction tasPlein(ref T:tas d'objet):booleen;
début
retourner(T.tailleTas==tailleStock)
fin
fonction setValeur(ref T:tas d'objet;val s:sommet;val x:objet):vide;
début
T.arbre[s]=x;
fin
fonction créerTas(ref T:tas d'objet; val x:objet):vide;
début
T.arbre[1]=x;
T.tailleTas=1;
fin
fonction ajouter(ref T:tas d'objet, val v:entier):vide
début
T.tailleTas=T.tailleTas+1;
T.arbre[T.tailleTas]=v;
reorganiseTasMontant(T,tailleTas);
fin
fonction reorganiseTasMontant(ref T: tas d'objet;val x:sommet):vide;
var p:sommet;
var signal:booléen;
début
p=père(x);
signal=vrai;
tantque x!=1 et signal faire
si getValeur(T,x)>getValeur(T,p) alors
échanger(T.arbre[p],T.arbre[x])
x=p;
p=père(x);
sinon
signal=faux
finsi
fintantque
fin
fonction supprimer(ref T:tas d'objet):vide;
var r:objet;
début
r=valeur(T);
T.arbre[1]=T.arbre[T.tailleTas];
T.tailleTas=T.tailleTas-1;
reorganiseTasDesc(T,1);
fin
fonction reorganiseTasDesc(ref T:tas d'objet,x:sommet):vide;
var g,d:sommet;
début
g= filsGauche(x);
d= filsDroit(x);
si g!=NIL alors
si d!=NIL alors
si getValeur(T,d)>getValeur(T,g) alors
g=d;
finsi;
finsi
si getValeur(T,x)<getValeur(T,g) alors
échanger(T.arbre[x],T.arbre[g]);
reorganiseTasDesc(T,g)
finsi
finsi
fin
Définition 7.5 Une file de priorité est un tas dans lequel on a la possibilité de modifier les valeurs des sommets.On dispose donc d'une primitive supplémentaire que l'on implémente et qui enrichit le type tas.
fonction changeValeur(ref T:tas d'objet,val s:sommet,val v:objet):vide;
début
setValeur(T,s,v);
si v> getValeur(T,pere(s)) alors
reorganiseTasMontant(T,s)
sinon
si v<getValeur(T,filsDroit(s))
ou v<getValeur(T,filsGauche(s)) alors
reorganiseTasDesc(T,s)
finsi
finsi
fin
Propriété 7.6 Le changement de valeur dans une file de priorité de taille n s'effectue en O(log(n)).