Tas binaire

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

Un tas binaire est une structure de données en informatique utilisée notamment pour implémenter les files 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 deux contraintes :

  • c'est un arbre binaire parfait : tous les niveaux excepté le dernier doivent être totalement remplis et si le dernier n'est pas totalement remplis 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)

Lorsque les étiquettes sont des nombres et la relation d'ordre choisie est l'ordre naturel on parle alors de tas-max (ou max-heap). Si l'on remplace "supérieure ou égal" par "inférieur ou égal" on parle alors de tas-min (ou min-heap).

Implémentation[modifier | modifier le code]

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

  • La racine se situe à l'index 0
  • Soit un nœud à l'index i alors son fils gauche est à l'index 2i+1 et son fils droit à 2i+2
  • Soit un nœud à l'index i>0 alors son père est à l'index \frac{i-1}{2}


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 i sont 2i et 2i+1 et l'indice du père est i/2. 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é : O(log\ n)

Considérons que l'on veuille ajouter le nœud x à notre tas binaire :
On insère x à la prochaine position libre (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 x n'est pas la racine de l'arbre et que x est strictement supérieur à son père on échange les positions entre x et son père.


Soit h la hauteur de notre tas binaire, lors de l'algorithme ci-dessus on effectue au plus h échanges. Or comme un tas binaire est un arbre binaire complet on a  h \le C\times log\ n (où n est le nombre de nœuds du tas binaire et C une constante) donc la complexité est bien O(log\ n) .


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


MaxHeapInsert0.svg

On insère 50 à la prochaine position libre

MaxHeapInsert1bis.svg

On compare 50 et son père 28, comme 50>28 on échange les positions de 50 et 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, on a fini de modifier notre arbre, à présent il respecte toutes les contraintes.

Résultat final de l'insertion de 50

Retirer[modifier | modifier le code]

Complexité : O(log\ n)

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 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 (donc le nœud le plus à droite sur le dernier niveau) que l'on notera x. Puis on fait l'opération suivante (que l'on appelle percolation vers le bas ou percolate-down) : tant que x a des fils et que x est strictement inférieur à un des ses fils, on échange les positions entre x et le plus grand de ses fils.

Par le même argument que pour l'algorithme de ajouter, on fait au plus h échange donc la complexité est bien O(log\ n)


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 c'est 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 donc on a fini. On a rétabli les propriétés d'ordre et de structure.


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é : O(h(x))h(x) est la profondeur de x


On augmente la clé de notre noeud x, 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 x n'est pas la racine et est strictement supérieur à son père on échange les positions entre x et son père.

Percolate-down[modifier | modifier le code]

Complexité : O(h-h(x))h(x) est la profondeur de x et h la hauteur de l'arbre


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

Construire[modifier | modifier le code]

Complexité : O(n)

On souhaite construire un tas binaire à partir d'un ensemble d'élément. 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 O(n\ log\ n). Ce n'est pas optimal, il existe une manière de construire notre tas binaire en O(n) [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 n.

2. On parcourt les sommets niveau par niveau en partant de l'avant dernier niveau (profondeur h-1) 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 de l'arbre notre arbre vérifie également l'invariant donc notre arbre est un tas binaire.


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

Soit h la hauteur de notre arbre (il y a donc h niveaux qui vont de 0 à h-1) et n le nombre de sommets. On se place dans le pire des cas, à chaque percolate-down on effectue le nombre maximal d'échange qui est  h-1-h(x) , le coût total de construire est donc :  C = \sum_{i=0}^{h-1} 2^{i}(h-1-i) par changement de variable  j=h-1-i dans la somme on a :  C = 2^{h-1} \sum_{j=1}^{h-1} j \frac{1}{2^j}
 Or j \frac{1}{2^j} =o(\frac{2^j}{3^j}) et \sum \frac{2^j}{3^j} converge comme série géométrique donc la série  \sum j \frac{1}{2^j} converge, d'où  C=O(2^{h-1})

On a également  2^{h-2} \le n donc finalement  C =O(n) .


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]