Que signifie le tas ?
Un tas, dans le contexte de la structure de données, est une structure de données arborescente qui satisfait à la propriété du tas, dans laquelle chaque élément se voit attribuer une valeur clé, ou pondération. La clé de valeur inférieure a toujours un nœud parent avec une clé de valeur supérieure. C'est ce qu'on appelle une structure à tas maximum, et parmi tous les nœuds, le nœud racine a la clé la plus élevée.
Parfois, une structure arborescente a une règle de structure inversée, selon laquelle un élément avec une clé de valeur supérieure a toujours une clé de valeur inférieure en tant que nœud parent. C'est ce qu'on appelle une structure min-heap, et parmi tous les nœuds, le nœud racine a la clé la plus basse.
Weendoz explique le tas
Il n'y a aucune restriction pratique sur le nombre d'enfants que chaque nœud peut avoir dans un tas, même si chaque nœud en a généralement deux au maximum. Le tas est considéré comme l’implémentation la plus efficace d’un type de données abstrait, appelé file d’attente prioritaire. L'implémentation du tas est essentielle dans divers algorithmes de graphes (y compris l'algorithme de Dijkstra) ainsi que dans l'algorithme de tri par tas.
Les tas présentent plusieurs variantes qui agissent comme des implémentations de files d'attente prioritaires de types de données abstraits avec une grande efficacité. De nombreuses applications, telles que les algorithmes graphiques, nécessitent la mise en œuvre de files d'attente prioritaires.
Un tableau est la forme d’implémentation de tas la plus courante, où aucun pointeur n’est nécessaire pour établir un lien entre ses éléments.
Les tas effectuent plusieurs opérations, notamment :
- Find-max : recherche le nœud clé le plus élevé parmi un groupe de nœuds
- Find-min : recherche le nœud clé le plus bas parmi un groupe de nœuds
- Supprimer-max : supprime le nœud clé le plus élevé parmi un groupe de nœuds
- Supprimer-min : supprime le nœud clé le plus bas parmi un groupe de nœuds
Les tas incluent également des fonctions qui effectuent des modifications de fusion, d'insertion et de clé.