Un tas est une structure de données. C'est une sorte d'arbre avec la propriété intéressante que tout nœud a une valeur inférieure à n'importe lequel de ses enfants.
Cela ne lui donne qu'un ordonnancement partiel, donc si vous voulez trouver une valeur spécifique dans le tas, ce n'est pas facile. C'est un gros inconvénient par rapport à un arbre binaire, qui permet's de faire des recherches efficaces.
Mais l'avantage de relâcher cette contrainte est la vitesse. Il peut faire des insertions et des suppressions en temps log n, et vous pouvez visualiser la valeur minimale en temps constant.
Une utilisation de celui-ci est un tri de tas. Il fonctionne comme ceci
- mettre toutes vos valeurs dans un tas
- Les retirer d'un tas
C'est'un tri nlgn efficace en place. Mettre la valeur shinto un tas leur donne un ordre lâche, mais la valeur la plus basse est toujours à la racine, donc quand vous les retirez, cela redonne les valeurs dans l'ordre.
C'est aussi un bon choix pour implémenter une file d'attente prioritaire. Vous ajoutez des valeurs en fonction de leur priorité, et vous les récupérez par ordre de priorité. C'est beaucoup plus efficace que d'essayer de maintenir une liste triée à chaque étape.
C'est un bon choix de mettre en place une file prioritaire.