TD 2 - Les tas
Rappel: Un tas est un arbre binaire où un entier est associé à
chaque noeud (appelé sa valeur ou sa priorité) avec les propriétés
suivantes: il est quasi complet (tous les niveaux sont remplis sauf
éventuellement le dernier où tous les éléments sont rangés à gauche) et la
valeur (la priorité) d'un noeud est supérieure ou égale à celles de tous
ses fils.
On numérote les noeuds ligne par ligne : la racine est le noeud 1, son fils
gauche est le noeud numéro 2 et son fils droit le numéro 3
etc. L'implémentation d'un tas se fait en utilisant un tableau :
Tab[i] contient la valeur du noeud i pour i>0,
et Tas[0] contient le nombre de noeud du tas.
- Ecrire la procédure void Ajouter(vector<int> & T,int e) qui
ajoute dans le tas T l'entier e à sa place.
- Ecrire la fonction int Max(const vector<int> & T) qui retourne la
priorité la plus grande du tas et la fonction bool EstVide(const
vector<int> & T) qui retourne 1 (resp. 0) si le tas textbfT est vide
(resp. non vide).
- Ecrire la procédure void Tamiser(vector<int> & T, int n) qui transforme le
sous-arbre de racine n de manière à ce que la priorité d'un noeud
soit supérieure ou égale à celles de tous ses fils.
- Ecrire la procédure void Supprimer(vector<int> & T) qui supprime du tas le
noeud ayant la plus forte priorité et la fonction int
Extrairemax() qui extrait du tas le noeud ayant la plus forte priorité et
la retourne comme résultat.
- [Facultatif] Ecrire une procédure (void
ConstruireTas(vector<int> & T,const vector<int> & Aux))
efficace (en temps linéaire) qui, étant donné un tableau
d'entiers Aux, construit un tas T contenant ces éléments.
- Reprendre les exercices précédents en définissant une classe Tas
et en utilisant des méthodes pour les différentes opérations.
fl@lsv.ens-cachan.fr
Last modification: January 23, 2002