Tas binaire

Carte Commune · n° 230046

En informatique, un tas binaire est une structure de données utilisée notamment pour implémenter une file de priorité 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, appelée également clé ou key, de chaque nœud, doit être, soit supérieure ou égale, soit 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...

Lire sur Wikipédia · Image Ermishin, CC BY-SA 3.0