Tas et tri par tas

Pour représenter un tas, on utilise la structure suivante:

1. Mettre la définition de type dans un fichier tas.h.
2. Ajouter à tas.h le prototype d'une fonction int creerTas(Tas *t, int max) qui initialise un tas vide avec une capacité maximale pour stocker max entiers. La fonction renvoie 1 si la création s'est bien passée et 0 sinon. Créer un fichier tas.c et y ajouter la définition de la fonction. Quelle doit-être la valeur du champs dernier ?
3. Écrire une fonction void detruireTas(Tas *t) qui libère toute mémoire associée au tas *t. Attention ! Après un appel à cette fonction, le tas ne peut plus être utilisé.

Écrire une fonction int estTas(int tab[], int taille) qui vérifie qu'un tableau tab de taille taille représente un tas.

Écrire une fonction int minFils(Tas t, int indice) qui renvoie -1 si le noeud représenté par la case indice n'a pas de fils, sinon renvoie l'indice du noeud fils qui contient la plus petite étiquette.

Écrire une fonction int inserer(Tas *t, int elt) qui insère une valeur au tas, tout en respectant sa structure. La fonction renvoie 1 si l'insertion est correcte et 0 sinon.

Écrire une fonction int extraireMin(Tas *t, int *elt) qui extrait la valeur minimum d'un tas et la fait passer par adresse dans *elt, tout en conservant une structure de tas pour *t. La fonction renvoie 1 si l'extraction s'est bien passée et 0 sinon.

En utilisant ces fonctions écrire la fonction void trierTas(int tab[], int taille) qui effectue un tri en ordre décroissant du tableau tab.

• Combien d'éléments pouvez-vous trier en 10 secondes ? Comparer avec le tri par insertion, le tri rapide et le tri fusion.