Tas et tri par tas

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

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

1. Mettre la définition de type dans un fichier heap.h.
2. Ajouter à heap.h le prototype d'une fonction int create_heap(heap *h, 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 heap.c et y ajouter la définition de la fonction. Quelle doit-être la valeur du champs size ?
3. É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 int is_heap(heap *h) qui vérifie que *h représente un tas.

Écrire une fonction int insert_heap(heap *h, int val) 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 extract_min(heap *h, int *val) qui extrait la valeur minimum d'un tas et la fait passer par adresse dans *val, tout en conservant une structure de tas pour *h. La fonction renvoie 1 si l'extraction s'est bien passée et 0 sinon.

En utilisant ces fonctions écrire la fonction void heap_sort(int tab[], int taille) qui effectue un tri en ordre décroissant du tableau tab. Dans un premier temps, vous pouvez allouer un tas supplémentaire dans la fonction. Dans un deuxième temps, vous effectuez le tri sur place dans le tableau tab, sans utiliser de mémoire supplémentaire.

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