# Sujet de TP 4: Tas Binaire, suite

## Règles pour ce semestre

Vous travaillerez en binôme durant les TPs. Il ne sera pas possible de changer
de binôme en cours de semestre. 

Il est interdit de partager du code avec d'autres binômes ou de "s'en inspirer".

Toute ressemblance suspecte sera AUTOMATIQUEMENT considérée comme de la fraude
et sévèrement sanctionnée.

Chaque semaine, un rendu vous sera demandé (vous aurez jusqu'au dimanche soir pour 
rendre le TP si vous ne finissez pas à temps) via gitlab.

Vos travaux seront évalués une fois à mi-semestre et une fois à la fin du semestre.

## Exercice 1: Tas binaire avec extraction


Le nom de votre branche est constitué de vos numéros d'étudiants séparés par un _

`git checkout -b tp4_NUMERO1_NUMERO2`

Rajouter le fichier `AUTHORS.md` avec vos noms, prénoms et numéros d'étudiants.

Modifier la strcture de tas pour pouvoir extraire la clé de plus petite valeur.
On voudra connaître le nombre d'échanges effectués par cette opération.

## Exercice 2: Benchmark

Effectuez des expériences sur l’efficacité en temps et en mémoire de cette structure :

- dans le cas où l'on ajoute une valeur aléatoire avec un probabilité `p` et on extrait
la clé de valeur minimale avec probabilité `1-p`.

Les noms des fichiers pdf seront de la forme `fixed_binary_heap_extract_MESURE_LANGAGE.pdf`

## Exercice 3: Tas binaire dynamique

Modifier la structure de tas binaire en remplacant le tableau de taille fixe par un tableau dynamique.

Relancer toutes les expériences faites sur les tas binaires de taille fixe sur les tas binaires dynamiques.

Vous devez impérativement créer un programme distinct pour chaque expérience.

Le nom des fichiers `pdf` commencera par `dynamic_binary_heap_*`

## Exercice 4:  

Commentez le resultat de vos expériences dans un fichier `RAPPORT.md`

- Que se passe t-il lorsque l'on ajoute des opérations de suppression? En temps? En mémoire?

- La complexité amortie des opérations d’ajout et de suppression/extraction a t-elle changé sur les expériences
utilisant un tableau dynamique ? Pourquoi ?

A RENDRE AVANT DIMANCHE!