Tas binaire

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Un tas-max
Un tas-min

En informatique, un tas binaire est une structure de données utilisée notamment pour implémenter une file de priorité car elle permet d'accéder au maximum (resp. minimum) d'un ensemble en temps constant. On peut la représenter par un arbre binaire qui vérifie ces deux contraintes :

  • C'est un arbre binaire parfait : tous les niveaux sauf le dernier doivent être totalement remplis et si le dernier ne l'est pas totalement, alors il doit être rempli de gauche à droite.
  • C'est un tas : l'étiquette (qu'on appelle aussi clé ou key) de chaque nœud doit être supérieure ou égale (resp. inférieure ou égale) aux étiquettes de chacun de ses fils (la signification de supérieur ou égal dépend de la relation d'ordre choisie).

Si la relation d'ordre choisie est "supérieure ou égale", on parle alors de tas-max (ou max-heap). Si la relation est "inférieure ou égale", on parle alors de tas-min (ou min-heap).

Implémentation[modifier | modifier le code]

Un tas binaire est un arbre binaire parfait, on peut donc l'implémenter de manière compacte avec un tableau.

  • La racine se situe à l'index
  • Étant donné un nœud à l'index , son fils gauche est à l'index et son fils droit à
  • Étant donné un nœud à l'index , son père est à l'index (arrondi à l'entier l'inférieur).


Un tas binaire implémenté avec un tableau


Parfois dans un souci d'efficacité, on ignore l'indice 0 et place la racine à l'indice 1. Ainsi les indices des fils d'un nœud à l'index sont et et l'indice du père est . L'avantage est que le calcul de ces indices peut se faire simplement par des opérations logiques de décalage de bits, ce qui est plus efficace en pratique que des opérations arithmétiques.

Opérations[modifier | modifier le code]

Un tas binaire supporte les opérations suivantes :

  • Ajouter : ajout d'un élément dans le tas binaire
  • Retirer : renvoie la racine et l'enlève du tas
  • Augmenter (resp Diminuer) la priorité d'un élément : augmente (resp diminue) la clé de l'élément choisi et modifie l'agencement pour respecter les contraintes de tas binaire
  • Construire : construction du tas binaire à partir d'un ensemble d'éléments

Ajouter[modifier | modifier le code]

Complexité :

Considérons que l'on veuille ajouter le nœud à notre tas binaire :
On insère à la prochaine position libre, soit la position libre la plus à gauche possible sur le dernier niveau. Puis, on effectue l'opération suivante (que l'on appelle percolation vers le haut ou percolate-up) pour rétablir si nécessaire la propriété d'ordre du tas binaire : tant que n'est pas la racine de l'arbre et que est strictement supérieur à son père, on échange les positions de et son père.


Soit la hauteur de notre tas binaire. Lors de l'algorithme ci-dessus on effectue au plus échanges. Or, comme un tas binaire est un arbre binaire parfait, on a , avec le nombre de nœuds du tas binaire et une constante. La complexité est donc bien en .

Exemple : On insère 50 dans un tas-max.

MaxHeapInsert0.svg

On insère 50 à la position libre la plus à gauche.

MaxHeapInsert1bis.svg

On compare 50 et son père 28. Comme 50 > 28, on échange les positions de 50 et de 28.

MaxHeapInsert2bis.svg

On compare 50 et son père 41. Comme 50 > 41, on échange les positions de 50 et 41.

MaxHeapInsert3bis.svg

On compare 50 et son père 53. Comme 50 < 53, on n'échange pas les positions de 50 et 53, et on a fini de modifier notre arbre. Il respecte à présent toutes les contraintes d'un arbre binaire.

Résultat final de l'insertion de 50

Retirer[modifier | modifier le code]

Complexité :

On souhaite retirer la racine de notre tas binaire (c'est-à-dire le maximum de notre tas selon la relation d'ordre associée). Cependant, il faut là aussi conserver la structure de tas binaire après la suppression. On procède donc de la manière suivante :
On supprime la racine, et on met à sa place le nœud qui était en dernière position de l'arbre binaire, soit donc le nœud le plus à droite sur le dernier niveau, que l'on notera . Puis on fait l'opération suivante (que l'on appelle percolation vers le bas ou percolate-down) : tant que a des fils et que est strictement inférieur à l'un de ses fils, on échange les positions entre et le plus grand de ses fils.

Par le même argument que pour l'algorithme de ajouter, on fait au plus échange donc la complexité est bien

Exemple : On retire la racine du tas-max suivant :

MaxHeapRemove0.svg

On remplace donc la racine par le nœud en dernière position (ici, 20).

MaxHeapRemove1.svg

On compare 20 et son fils maximum, qui est 41. Comme 41 > 20, on échange 20 et 41.

MaxHeapRemove2.svg

On compare 20 et son fils maximum, qui est 36. Comme 36 > 20, on échange 20 et 36.

MaxHeapRemove3.svg

On compare 20 et son fils maximum, qui est 31. Comme 31 > 20, on échange 20 et 31.

MaxHeapRemove4.svg

20 n'a plus de fils, on a donc fini. Les propriétés d'ordre et de structure du tas sont rétablies.

Augmenter ou diminuer une clé[modifier | modifier le code]

On peut augmenter ou diminuer la priorité (la clé) d'un nœud mais il faut ensuite satisfaire la contrainte d'ordre. Si l'on augmente la clé on fera donc un percolate-up à partir de notre nœud et si l'on diminue la clé on fera un percolate-down.

Percolate-up[modifier | modifier le code]

Complexité : est la profondeur de


On augmente la clé de notre nœud , par conséquent il se peut qu'il devienne supérieur à son père et à d'autres nœuds au-dessus de son père. Pour maintenir la contrainte d'ordre on effectue donc l'opération suivante : tant que n'est pas la racine et est strictement supérieur à son père on échange les positions entre et son père.

Percolate-down[modifier | modifier le code]

Complexité : est la profondeur de et la hauteur de l'arbre


On diminue la clé de notre nœud , il se peut donc qu'il devienne inférieur à un de ses fils et à d'autres nœuds en dessous. Pour maintenir la contrainte d'ordre on effectue donc l'opération suivante : tant que a des fils et est strictement inférieur à un de ses fils on échange les positions entre et son fils maximum.

Construire[modifier | modifier le code]

Complexité :

On souhaite construire un tas binaire à partir d'un ensemble d'éléments. De manière naïve on part du tas vide et on ajoute les éléments un par un avec l'algorithme ajouter, ce qui donne une complexité en . Ce n'est pas optimal, il existe une manière de construire notre tas binaire en [1]:


1. On construit un arbre binaire avec tous les éléments sans se soucier de la contrainte d'ordre. Cela prend donc un temps linéaire en .

2. On parcourt les sommets niveau par niveau en partant de l'avant dernier niveau (profondeur ) et dans chaque niveau on parcourt les sommets de la droite vers la gauche. Lors de notre parcours on effectue un percolate-down à partir de chaque sommet.

Preuve de la correction[modifier | modifier le code]

On convient d'appeler sous-arbre d'un sommet dans un arbre le sous-arbre maximal dont ce sommet est la racine.

Pendant le parcours des sommets on maintient l'invariant suivant : Tous les sous-arbres des sommets à droite du sommet courant (sur le même niveau) sont des tas binaires. Donc après avoir traité la racine, comme elle vérifie l'invariant, notre arbre est un tas binaire.


Preuve de la complexité[modifier | modifier le code]

Soit la hauteur de notre arbre (il y a donc niveaux qui vont de à ) et le nombre de sommets. Dans le pire cas, chaque percolate-down effectue le nombre maximal d'échange qui est . Le coût total de construire est donc majoré par . Par le changement de variable dans la somme on obtient : .
 Or et converge car c'est une série géométrique de raison strictement inférieure à 1. Donc la série converge, d'où . Mais donc finalement .

Références[modifier | modifier le code]

  1. Knuth D.E. The Art of Computer Programming, Vol. III Sorting and Searching Addison-Wesley Professional; 2 edition (May 4, 1998)


Liens externes[modifier | modifier le code]