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).
Un tas (min) permet les opérations suivantes:
insert
: \(O(\log(n))\)peek
: \(O(1)\)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 :
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`
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 :
Les étiquettes (valeurs) des nœuds sont stockés dans le tableau aux indices correspondant.
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.
bubble_up
percolate_down
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.
asort
tel qu’il respecte les exigences de la section [cas d’utilisation]is_heap_empty
et la fonction heap_peek
.parent
, left
et right
. Puis la fonction is_valid
heap_insert
, pour cela vous devrez réaliser et utiliser swap
, bubble_up
.heap_pop
, pour cela vous devrez réaliser et utiliser percolate_down
.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
.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).heapify
, qui étant donné un tableau, construit un tas (valide, cela va sans dire).heap_sort
.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);
}
Il est possible que je vous présente cette étape avant la partie télécharger ↩