Tas binaire
En informatique, un tas binaire est une structure de données utilisée notamment pour implémenter une car elle permet de retirer l’élément de priorité maximale (resp. minimale) d'un ensemble ou d’insérer un élément dans l'ensemble en temps logarithmique tout en conservant la structure du tas binaire. On peut la représenter par un arbre binaire qui vérifie ces deux contraintes : C'est un arbre binaire complet : 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). 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 inférieur). 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. 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 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.
