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.

1. Ecrire la procédure void Ajouter(vector<int> & T,int e) qui ajoute dans le tas T l'entier e à sa place.
2. 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).
3. 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.
4. 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.
5. [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.
6. Reprendre les exercices précédents en définissant une classe Tas et en utilisant des méthodes pour les différentes opérations.