J'utilise une structure de données que le développeur d'origine a appelée heap, il est utilisé pour mettre en oeuvre une file d’attente prioritaire.
Bien qu'il y ait beaucoup d'écrits sur les arbres binaires, les tas (min / max) semblent moins bien définis (les détails varient selon les implémentations).
Certaines caractéristiques que j’ai "remarquées" ne s’appliquent pas nécessairement aux structures d’arbres binaires.
- Le même élément peut se trouver plusieurs fois dans la file d'attente sans compliquer l'exécution ou la mise en œuvre.
- Recherche (bien que possible et plus rapide qu'une recherche exhaustive), n’est pas aussi efficace (car les éléments enfants de chaque noeud ne doivent pas être équilibrés).
- Comme la recherche n’est pas efficace et qu’il existe un risque de duplication, il peut être nécessaire de stocker une référence à la
node, au lieu d'utiliser unkeypour rechercher le nœud (pratique courante pour les arbres binaires). - Changer les priorités dans le tas est trivial, comparé à un arbre binaire où il est le plus courant de supprimer + insérer.
(avec un meilleur meilleur cas et un pire cas comparé aux arbres binaires)
Existe-t-il une terminologie plus détaillée pour les structures de données qui correspondent à ces caractéristiques?
Ou est-ce simplement un min/max heap qui se trouve être utilisé comme priority-queue?
Remarque, voici un lien vers un min-tas qui présente les caractéristiques décrites ci-dessus.
Réponses:
2 pour la réponse № 1UNE tas binaire est une mise en œuvre concrète du File d'attente de priorité structure de données abstraite. Il est populaire car il est facile à implémenter, efficace en mémoire et assez rapide: insertion O (log n) et suppression O (log n) de la racine (la plus petite dans un segment min, la plus grande dans un segment max) . La plupart des implémentations fournissent également une méthode de lecture qui permet de visualiser l'élément racine sans le supprimer.
Un tas binaire ne fait rien d'autreparticulièrement bien. Contrairement à votre observation, trouver un élément particulier dans un tas binaire nécessite une analyse séquentielle. Bien que les nœuds soient ordonnés (non triés), la commande ne se prête pas bien à la recherche.
L'implémentation typique d'un tas binaire est dans un tableau. En raison de propriété de forme (la structure peut être considérée comme parfaite (oucomplet) arbre binaire), ce qui signifie que la relation entre parent et enfant est représentée implicitement. Les éléments sont stockés dans le tableau en ordre de priorité.
Comme l’a souligné l’utilisateur templatetypedef dans sonréponse, un tas binaire est un type spécifique d'arbre binaire, et ne doit pas être confondu avec un arbre de recherche binaire, qui est spécialement conçu pour l'insertion et la suppression rapides d'éléments, et la localisation d'éléments par clé.
Bien que la modification de la priorité d'un élément dans le segment de mémoire ou la suppression d'un élément arbitraire du segment de mémoire soient très faciles, le problème, comme vous l'avez souligné, est localiser l'article à opérer. Dans un tas binaire typique, la recherche de l'élément à modifier nécessite une recherche séquentielle. Si vous avez besoin de pouvoir déplacer des éléments dans le tas, vous devez généralement marier le binaire avec un dictionnaire ou une carte de hachage qui est indexée par la clé de l'élément. La valeur est l'index de l'élément dans le tableau. Cet index est mis à jour chaque fois qu'un élément est déplacé. Cela ralentit les opérations de tas d'un facteur constant, mais vous donne la possibilité de localiser un élément dans O (1).
Il y a aussi quelque chose appelé Tas min-max, qui est un type de tas binaire qui vous donne un accès O (1) à la fois aux éléments min et max. L'implémentation est très similaire à l'implémentation d'un segment de mémoire binaire standard.
Pour confondre encore plus les choses, il existe aussile tas d-aire, qui est un tas qui contient plus de deux enfants par nœud. Par exemple, un tas trinaire a trois enfants par nœud. Celles-ci sont également implémentées dans des tableaux avec des pointeurs enfants implicites.
Il existe d'autres structures de données qui sont généralementappelés tas, mais ne sont en fait pas vraiment liés au tas, sauf qu'ils sont des implémentations différentes de la structure de données de file d'attente prioritaire. Les plus populaires semblent être le tas de couplage, le tas de Fibonacci et le tas binomial, qui peuvent également être implémenté avec des arbres binaires. (Encore une fois, pas des arbres de recherche binaires.)
J'ai écrit une introduction quelque peu guidée aux tas binaires (et aux tas d-aires) dans mon blog il y a quelques années. Si vous êtes intéressé, consultez cette entrée, qui répertorie tous les articles de cette série.
2 pour la réponse № 2
Je pense que vous confondez binaire chercher arbres et arbres binaires. Un arbre binaire est plus une forme qu'autre chose - c'est un arbre où chaque nœud a au plus deux enfants. Les nœuds ne doivent pas nécessairement contenir de valeurs, et s’ils le font, il n’est pas nécessaire qu’ils obéissent à des règles particulières.
Un binaire chercher arbre est un arbre binaire où chaque nœud contient unet chaque nœud obéit à la règle selon laquelle toutes les clés du sous-arbre gauche sont inférieures à la clé du nœud et toutes les clés du sous-arbre droit sont supérieures à la clé du nœud. (Certaines définitions assouplissent l'exigence de permettre un nombre inférieur ou égal à au lieu d'un peu moins, etc.)
Il existe de nombreuses autres structures de données construites à partir d'arbres binaires qui ne sont pas des BST. Les arbres k-d stockent des données multidimensionnelles. Le binaire essaie de stocker des chaînes de bits.
Je pense donc que la meilleure description ici est «binaireles tas sont des arbres binaires qui sont complets et obéissent à la propriété du tas, qui n'est pas la même chose qu'un arbre de recherche binaire même s'ils ont la même forme sous-jacente (plus ou moins). "