Tas

Description

Un tas est un type concret utilisé pour dans l'algorithme de tri par tas, et pour implémenter le type abstrait file de priorité.

On peut décrire un tas de manière abstraite comme un arbre binaire avec deux restrictions.

Premièrement, le domaine doit être ordonné. Chaque sommet de l'arbre contient un élément du domaine, et le père (s'il existe) d'un sommet s doit contenir un élément inférieur ou égal à celui contenu dans s.

Deuxièmement, si l'on numérote la racine de l'arbre 1 et récursivement les fils d'une sommet i 2i (fils gauche) et 2i+1 (fils droit) respectivement, alors quelque soit k > 1, si le sommet k existe dans l'arbre, alors, le sommet k-1 existe aussi. Une autre façon d'exprimer cette restriction est que l'arbre doit être rempli du haut en bas et de gauche à droite.

La deuxième restriction permet de stocker un tas dans un tableau avec le sommet i à la place i-1 dans le tableau (les tableaux sont indexés à partir de 0). Alternativement, on peut accepté de gaspiller la place 0 du tableau et stocker le sommet i à la place i du tableau pour simplifier les calculs nécessaires pour la manipulation du tas.

En fait, le calcul pour trouver les fils ou le père d'un sommet i est particulièrement simple : Pour trouver le fils gauche d'un sommet i il suffit de décaler i à gauche d'une position (une opération extrêmement efficace). Pour trouver le fils droit il suffit de d'abord décaler i à gauche puis de rajouter 1 au résultat. Pour trouver le parent d'un sommet i, il suffit de décaler i à droite d'une position.

Opérations

Il y a deux opérations de base possibles sur un tas : insérer un élément arbitraire et remplacer l'élément le plus petit par un élément arbitraire.

Il est également possible de supprimer l'élément le plus petit (sans le remplacer). Il suffit pour cela de le remplacer par le dernier élément du tas (celui qui se trouve à la place numéro n).

Insérer un élément arbitraire

Si le tas a n éléments, on commence par insérer le nouvel élément à la place n+1. Le résultat est un arbre qui n'est pas forcement un tas, car il est entièrement possible que l'élément ainsi inséré soit plus petit que son père. Il faut donc ajuster.

Pour ajuster, on compare le nouvel élément avec son père. Si l'élément est plus petit que le père, alors on échange les deux, et on considère à nouveau l'élément à sa nouvelle place. Ce processus se termine lorsque l'élément n'a pas de père ou lorsque le père est plus petit que, ou égal à, l'élément.

Pour réaliser que le résultat de ce processus est un tas, on remarque que le sous arbre ayant comme sommet le nouvel élément est toujours un tas, et qu'à chaque échange de l'élément et son père, le sous arbre est étendu. Remarque : si un élément est plus petit que son père, il est également plus petit que son frère (car le père est plus petit que le frère). L'échange de l'élément avec son père dans cette situation ne peut donc pas avoir de conséquences négatives sur le sous arbre du frère.

Remplacer l'élément le plus petit par un élément arbitraire

Le plus petit élément se trouve à la racine de l'arbre. On commence cette opération par mettre le nouvel élément à la place de l'élément le plus petit. Le résultat est un arbre que n'est pas forcement un tas. Encore une fois, il faut donc ajuster

Pour ajuster, on compare le nouvel élément avec ces deux fils. Si chacun des deux fils est plus grand que, ou égal à, l'élément, nous avons un tas. Sinon, on échange l'élément avec le plus petit des deux fils. Si les deux fils sont égaux, on peut choisir l'un des deux arbitrairement. Si l'élément n'a qu'un seul fils, ce celui-là qui sera choisi. Puis, on considère l'élément à sa nouvelle place avec les deux nouveaux fils. Le processus se termine lorsque l'élément n'a pas de fils, ou lorsque aucun des fils n'est plus petit que l'élément.