TP6 - Tri par tas
Informatique - Licence Science & Technique MI,
L2.2
Le but de ce TP est de réaliser un algorithme de tri en un
temps O( n log n ).
Pour ce faire nous allons implementer une nouvelle structure
d'arbre complet partiellement trié, basé sur un
tableau. " Le Tas ". Chaque noeud de l'arbre contient une
valeure plus petite que toutes celles de ses fils. Mais aucune
information n'est donnée quand a la comparaison entre les deux
fils d'un noeud.
On considère la déclaration suivante de la structure
classique d'un tas.
typedef struct {
int *t;
int n;
} tas;
Figure 1. Exemple d'insertion d'une suite d'entiers.
Exercice 1- Fonctions de base
Réaliser une fonction d'initialisation d'un tas.
Réaliser une fonction d'insertion d'un entier dans un
tas: int insertionTas(tas *t, int n)
la valeur retournée permet de verifier si l'insertion c'est bien
déroulée.
Exercice 2- Suppresion dans un tas.
Ecrire une fonction permettant la suppression du premier élément
de l'arbre, et qui retourne cette valeur.
Attention : Le tas doit garder toutes ses propriétés....
Exercice 3- Algorithme de tri.
Implémenter une fonction permettant d'ajouter une serie de
n entiers dans le tas int insertion (tas *t,
int n), en utilisant la fonction precedente.