Définition - Que signifie Heap?
Un tas, dans le contexte de la structure de données, est une structure de données basée sur une arborescence qui satisfait la propriété de tas, où chaque élément se voit attribuer une valeur de 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 de 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, où un élément avec une clé de valeur plus élevée a toujours une clé de valeur inférieure comme nœud parent. C'est ce qu'on appelle une structure de tas min, et parmi tous les nœuds, le nœud racine a la clé la plus basse.
Definir Tech explique Heap
Il n'y a pas de restrictions pratiques 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 heapsort.
Les tas ont plusieurs variances qui agissent comme des implémentations de file d'attente de priorité de type de données abstraites avec une efficacité élevée. 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 la plus courante de tas, 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 de clé le plus élevé parmi un groupe de nœuds
- Find-min: recherche le nœud de clé le plus bas parmi un groupe de nœuds
- Delete-max: supprime le nœud de clé le plus élevé d'un groupe de nœuds
- Delete-min: supprime le nœud de clé le plus bas d'un groupe de nœuds
Les tas incluent également des fonctions qui effectuent la fusion, l'insertion et les modifications clés.
Cette définition a été écrite dans le contexte de la structure des données