Tas et tri par tas

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

typedef struct {
  int *tree;
  int size;
  int max;
} heap;

1. Mettre la définition de type dans un fichier heap.h.
2. Ajouter à heap.h le prototype d'une fonction heap *create_heap(int max) qui alloue, initialise et renvoie un pointeur sur un tas vide avec une capacité maximale pour stocker max entiers.
3. Créer un fichier heap.c et y ajouter la définition de la fonction. Quelle doit-être la valeur du champs size ?
4. Écrire une fonction void free_heap(heap *h) qui libère toute mémoire associée au tas *h. Attention ! Après un appel à cette fonction, le tas ne peut plus être utilisé.

Écrire une fonction void insert_heap(heap *h, int elt) qui insère une valeur au tas, tout en respectant sa structure.

Écrire une fonction int is_heap(heap *h) qui vérifie que *h représente un tas. L'utiliser pour vérifier que la fonction insert_heap est correcte.

Écrire une fonction int extract_min(heap *h) qui extrait et renvoie la valeur minimum d'un tas, tout en conservant une structure de tas pour *h.

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

1. Dans un premier temps, vous pouvez allouer un tas supplémentaire dans la fonction.
2. Dans un deuxième temps, vous effectuez le tri sur place dans le tableau tab, sans utiliser de mémoire supplémentaire.

Comparer la fonction heapsort avec la fonction quicksort implantée au tp 4. Combien d'éléments aléatoires pouvez-vous trier en 1, 2, ..., 20 secondes ? Tracer un diagramme en utilisant l'outil gnuplot (voir l'exercice 5 du tp 4). Comparer également le comportement des deux algorithmes sur d'autres types de données, par exemple sur des tableaux déjà triés, inversés ou avec peu de clés distinctes.