Types de Données: Le tas

Un tas (binaire) est un arbre (binaire) presque complet, i.e., tous les niveaux sont pleins, sauf éventuellement le dernier, sur la droite, muni d’une relation d’ordre ou la valeur de chaque nœud est inférieure (resp. supérieure) à la valeur de ses enfants. Nous appellerons cette propriété un invariant du tas.

Un tas permet de retourner l’élément le plus petit (resp. grand) en temps constant (sans boucle), et de le retirer en temps logarithmique (i.e., pas trop cher même pour des grands ensembles). Il est totalement indiqué lorsque les éléments sont découverts au fur et à mesure du traitement (i.e., là ou on ne peut pas se limiter à faire un tri une bonne fois pour toute).

Opérations

Un tas (min) permet les opérations suivantes:

  • Ajouter un élément, insert : \(O(\log(n))\)
  • Retourner l’élément le plus petit (le plus grand), peek : \(O(1)\)
  • Retirer le plus petit (le plus grand), pop : \(O(\log(n))\)

A ces opérations spécifiques, on peut (doit!) y adjoindre les fonctions d’allocation/initialisation et de libération, des fonctions sur l’état, comme : est il vide ? ou, quelle est sa taille ?

Ce type a de nombreuses utilisation algorithmiques dont :

  • les files de priorités (sera utilisé dans Huffman)
  • le tri par tas (plus ou moins ce tp)

Cas d’utilisation

Nous réaliserons le programme asort qui affichera ses arguments triés sur la sortie standard (stdout, i.e.,printf).

./asort foo bar baz papa tata maman bateau
bar
bateau
baz
foo
maman
papa
tata

Pour se faire nous utiliserons un tas, dans lequel nous insèrerons tous les arguments de notre programme (argv), puis nous les retirerons et les afficherons un à un. Pour cet exemple bien précis, la variante en-place du tri par tas serait plus efficace, cependant elle est laissée en bonus à l’étudiant aguerri;

déclarer un tas `h` de capacité `argc` - 1, avec `strcmp` comme comparateur.

Pour chaque argument du programe (`argv`):
    inserer `argv[i]` dans `h`

Tant que le tas `h` n est pas vide:
    sortir un élement `e` du tas `h`
    afficher `e`

Représentation des arbres complets sous forme de tableau

Il existe une projection sous forme de tableau des arbres binaires (presque) complets. En numérotant les nœuds de l’arbre, en partant de la racine, de gauche a droite étage par étage, un parcours en largeur , on obtient les trois fonctions de navigation suivantes :

  • fils gauche : \(2*i+1\)
  • fils droit : \(2*i+2\)
  • parent : \(\lfloor \frac{i-1}{2} \rfloor\)

Les étiquettes (valeurs) des nœuds sont stockés dans le tableau aux indices correspondant.

Algorithmes

Récupérer le plus petit élément est trivial : c’est la racine, i.e., le premier élément du tableau. Le prédicat is_empty est lui aussi trivial, il est vrai si et seulement si la taille est supérieure à zéro. Les deux opérations d’insertion et de suppression sont elles plus complexes et reposent sur deux sous fonctions : bubble_up et percolate_down. L’idée est de partir d’un presque tas, un tas ou seul un élément est mal placé, et de restaurer l’invariant du tas : Tout élément est plus petit (dans la relation d’ordre) que ses enfants.

Insertion : bubble_up

  • On ajoute au premier emplacement disponible, i.e., le plus a gauche possible du dernier étage, i.e., à la fin du tableau.
  • On fait remonter cet élément vers la racine jusqu’à ce que le tas revérifie sa propriété : tout élément n’a pas de valeur supérieure (resp. inférieure) au dessus de soi.
  • I.e., On répète, tant qu’on doit permuter un élément et son parent (de l’élément ajouté à la racine).

Exemple d’insertion

Retrait : percolate_down

  • On échange la racine avec le dernier emplacement utilisé, i.e., le plus a gauche possible du dernier étage, i.e., à la fin du tableau (section suivante)
  • On fait descendre cet élément vers la première case où il revérifiera la propriété.
  • A chaque tour, tant qu’on a permuté, on cherche l’élément le plus petit entre l’élément courant, son fils gauche, et son fils droit, et on les permutes si nécessaire.

Exemple de supression

Travail demandé

  1. Récupérer le code dans vos dépôts (probablement déjà fait)
  2. Télécharger une version de heap.o qui vous permettra de faire asort, votre main.

     make     'download(heap.o)'
    

    Pour macosx rajoutez OS=osx à la commande précédente.

  3. Faire le programme asort tel qu’il respecte les exigences de la section [cas d’utilisation]
  4. Écrire les fonctions nécessaire à l’initialisation d’un tas 1, le prédicat : is_heap_empty et la fonction heap_peek.
  5. Écrire les fonctions de navigations parent, left et right. Puis la fonction is_valid
  6. Écrire la fonction d’insertion, heap_insert, pour cela vous devrez réaliser et utiliser swap, bubble_up.
  7. Réaliser la fonction de suppression, heap_pop, pour cela vous devrez réaliser et utiliser percolate_down.
  8. Ajouter à l’ API du tas le prédicat heap_contains, qui retourne vrai si l’élément est présent dans le tas, et la fonction heap_remove, qui retire un élément du tas. Après avoir réaliser heap_contains se rendre compte qu’une partie du code est nécessaire pour heap_remove, l’extraire dans une fonction statique find_value.
  9. Bonus: Si on numérote les nœuds de l’arbre en commençant à un au lieu de zéro, les fonctions de navigations peuvent se simplifier à \(2i\), \(2i + 1\) et \(i/2\). Peut on utiliser cette astuce sans perdre de case dans le tableau ? Le réaliser (ce qui vous spoile la réponse précédente, allez je vous souffle, c’est oui … mais comment).
  10. Bonus: Faire la fonction heapify, qui étant donné un tableau, construit un tas (valide, cela va sans dire).
  11. Bonus: Implémenter le tri par tas heap_sort.

Le mode DEBUG

Par défaut les programmes C sont compilés en mode DEBUG (autant dire que si vous ne vous en servez pas, il ne se passera pas grand chose à la fin ;) ). Cela veut dire qu’il honore les directives telles que assert. Pour désactiver le mode débug pour un fichier, il suffit de le compiler avec l’option -DNDEBUG. On peut dire à make de le faire pour tous les fichiers (il faudra probablement faire un make clean avant) :

make CFLAGS+=-DNDEBUG

En mode debug, nous vous proposons la macro DEBUG(...) qui s’utilise comme un printf sans les erreurs classiques du printf.

assert(foo == bar); // C'est du debug

DEBUG("Bla bla"); // Ca aussi

for (int i=0; i < 3; ++i) {
  DEBUG("Un autre message du tour de boucle %d", i);
}

  1. Il est possible que je vous présente cette étape avant la partie télécharger