Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Tas binaire
Résumé
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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.