Tas binaire et tri par tas

Pour représenter un tas binaire, 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 binaire 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 binaire *h. Attention ! Après un appel à cette fonction, le tas binaire ne peut plus être utilisé.

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

Écrire une fonction int is_heap(heap *h) qui vérifie que *h représente un tas binaire. 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 binaire, tout en conservant une structure de tas binaire 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 binaire 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.