Heap vs arbre de recherche binaire (BST)

Quelle est la différence entre un tas et BST?

Quand utiliser un tas et quand utiliser un BST?

Si vous souhaitez obtenir les éléments de manière triée, BST est-il meilleur sur le tas?

Résumé

          Type      BST (*)   Heap
Insert    average   log(n)    1
Insert    worst     log(n)    log(n) or n (***)
Find any  worst     log(n)    n
Find max  worst     1 (**)    1
Create    worst     n log(n)  n
Delete    worst     log(n)    log(n)

Tous les temps moyens sur ce tableau sont les mêmes que leurs pires moments, sauf pour Insertion.

• *: partout dans cette réponse, BST == Balanced BST, puisque déséquilibré aspire asymptotiquement
• **: en utilisant une modification triviale expliquée dans cette réponse
• ***: log(n)pour le tas d'arborescence de pointeurs, npour le tas de tableaux dynamiques

Avantages du tas binaire par rapport à un BST

• le temps moyen d'insertion dans un tas binaire est O(1), pour BST est O(log(n)). C'est la caractéristique qui tue des tas.

  Il existe également d'autres tas qui atteignent l' O(1)amorti (plus fort) comme le tas de Fibonacci , et même le pire des cas, comme la file d'attente Brodal , bien qu'ils puissent ne pas être pratiques en raison de performances non asymptotiques: les tas de Fibonacci ou les files d'attente Brodal sont-ils utilisés en pratique n'importe où?

• Les tas binaires peuvent être efficacement implémentés sur des tableaux dynamiques ou des arbres basés sur des pointeurs, BST uniquement des arbres basés sur des pointeurs. Donc, pour le tas, nous pouvons choisir l'implémentation de tableau la plus économe en espace, si nous pouvons nous permettre des latences de redimensionnement occasionnelles.

• la création de tas binaire est le O(n)pire des cas , O(n log(n))pour BST.

Avantage de BST sur le tas binaire

• la recherche d'éléments arbitraires est O(log(n)). C'est la fonctionnalité qui tue des BST.

  Pour le tas, c'est O(n)en général, sauf pour le plus grand élément qui est O(1).

"Faux" avantage du tas par rapport à BST

• tas est O(1)de trouver max, BST O(log(n)).

  C'est une idée fausse courante, car il est trivial de modifier un BST pour garder une trace du plus grand élément, et de le mettre à jour chaque fois que cet élément pourrait être modifié: lors de l'insertion d'un plus grand swap, lors de la suppression, trouvez le deuxième plus grand. Pouvons-nous utiliser l'arbre de recherche binaire pour simuler le fonctionnement du tas? (mentionné par Yeo ).

  En fait, c'est une limitation des tas par rapport aux BST: la seule recherche efficace est celle du plus grand élément.

L'insertion de tas binaire moyenne est O(1)

Sources:

• Papier: http://i.stanford.edu/pub/cstr/reports/cs/tr/74/460/CS-TR-74-460.pdf
• Diapositives WSU: http://www.eecs.wsu.edu/~holder/courses/CptS223/spr09/slides/heaps.pdf

Argument intuitif:

• les niveaux inférieurs de l'arborescence ont exponentiellement plus d'éléments que les niveaux supérieurs, de sorte que les nouveaux éléments sont presque certains d'aller en bas
• l'insertion du tas commence par le bas , BST doit commencer par le haut

Dans un tas binaire, augmenter la valeur à un index donné est également O(1)pour la même raison. Mais si vous voulez faire cela, il est probable que vous souhaitiez garder un index supplémentaire à jour sur les opérations de tas . par exemple pour Dijkstra. Possible sans frais de temps supplémentaire.

Benchmark d'insertion de bibliothèque standard GCC C ++ sur du matériel réel

J'ai comparé l' insertion C ++ std::set( arbre rouge-noir BST ) et std::priority_queue( tas de tableau dynamique ) pour voir si j'avais raison sur les temps d'insertion, et voici ce que j'ai obtenu:

• code de référence
• script de tracé
• données de tracé
• testé sur Ubuntu 19.04, GCC 8.3.0 dans un ordinateur portable Lenovo ThinkPad P51 avec CPU: CPU Intel Core i7-7820HQ (4 cœurs / 8 threads, 2,90 GHz de base, 8 Mo de cache), RAM: 2x Samsung M471A2K43BB1-CRC (2x 16GiB , 2400 Mbps), SSD: Samsung MZVLB512HAJQ-000L7 (512 Go, 3 000 Mo / s)

Donc clairement:

• le temps d'insertion du tas est fondamentalement constant.

  Nous pouvons clairement voir les points de redimensionnement du tableau dynamique. Étant donné que nous calculons en moyenne tous les 10 000 inserts pour pouvoir voir quoi que ce soit au-dessus du bruit du système , ces pics sont en fait environ 10 000 fois plus grands que ceux indiqués!

  Le graphique agrandi exclut essentiellement uniquement les points de redimensionnement du tableau et montre que presque tous les insertions tombent sous 25 nanosecondes.

• BST est logarithmique. Toutes les insertions sont beaucoup plus lentes que l'insert de tas moyen.

• Analyse détaillée BST vs hashmap sur: Quelle structure de données se trouve à l'intérieur de std :: map en C ++?

Benchmark d'insertion de bibliothèque standard GCC C ++ sur gem5

gem5 est un simulateur système complet, et fournit donc une horloge infiniment précise avec avec m5 dumpstats. J'ai donc essayé de l'utiliser pour estimer les horaires des inserts individuels.

Interprétation:

• le tas est toujours constant, mais maintenant nous voyons plus en détail qu'il y a quelques lignes, et chaque ligne supérieure est plus clairsemée.

  Cela doit correspondre aux latences d'accès à la mémoire pour les insertions de plus en plus élevées.

• TODO Je ne peux pas vraiment interpréter le BST complètement car il n'a pas l'air si logarithmique et un peu plus constant.

  Cependant, avec ce plus de détails, nous pouvons également voir quelques lignes distinctes, mais je ne suis pas sûr de ce qu'elles représentent: je m'attendrais à ce que la ligne du bas soit plus mince, puisque nous insérons du haut en bas?

Testé avec cette configuration Buildroot sur un processeur HPI aarch64 .

BST ne peut pas être mis en œuvre efficacement sur une baie

Les opérations de tas n'ont besoin que de remonter ou descendre une seule branche d'arbre, donc dans le O(log(n))pire des cas, les échanges sont O(1)moyens.

Garder un BST équilibré nécessite des rotations d'arbre, ce qui peut changer l'élément supérieur pour un autre, et nécessiterait de déplacer tout le tableau autour de ( O(n)).

Les tas peuvent être efficacement implémentés sur un tableau

Les index parents et enfants peuvent être calculés à partir de l'index actuel, comme illustré ici .

Il n'y a pas d'opérations d'équilibrage comme BST.

Supprimer min est l'opération la plus inquiétante car elle doit être descendante. Mais cela peut toujours être fait en "percolant" une seule branche du tas comme expliqué ici . Cela conduit au pire des cas O (log (n)), puisque le tas est toujours bien équilibré.

Si vous insérez un seul nœud pour chaque nœud que vous supprimez, vous perdez l'avantage de l'insertion moyenne asymptotique O (1) fournie par les tas, car la suppression dominerait, et vous pourriez aussi bien utiliser un BST. Cependant, Dijkstra met à jour les nœuds plusieurs fois pour chaque suppression, donc tout va bien.

Tas de tableaux dynamiques vs tas d'arbres de pointeurs

Les tas peuvent être efficacement implémentés au-dessus des tas de pointeurs: est-il possible de faire des implémentations de tas binaires basées sur des pointeurs efficaces?

La mise en œuvre de la matrice dynamique est plus efficace en termes d'espace. Supposons que chaque élément de tas contienne juste un pointeur vers a struct:

• l'implémentation de l'arborescence doit stocker trois pointeurs pour chaque élément: parent, enfant gauche et enfant droit. Ainsi, l'utilisation de la mémoire est toujours 4n(3 pointeurs d'arbre + 1 structpointeur).

  Les BST d'arbre auraient également besoin d'informations supplémentaires d'équilibrage, par exemple noir-rouge-ness.

• l'implémentation du tableau dynamique peut être de taille 2njuste après un doublement. Donc, en moyenne, ça va être 1.5n.

D'un autre côté, le tas d'arborescence a une meilleure insertion dans le pire des cas, car la copie du tableau dynamique de sauvegarde pour doubler sa taille prend le O(n)pire des cas, tandis que le tas d'arborescence ne fait que de nouvelles petites allocations pour chaque nœud.

Néanmoins, le doublement de la matrice de support est O(1)amorti, ce qui revient à une considération de latence maximale. Mentionné ici .

Philosophie

• Les BST conservent une propriété globale entre un parent et tous les descendants (plus petit à gauche, plus grand à droite).

  Le nœud supérieur d'un BST est l'élément du milieu, ce qui nécessite des connaissances globales à maintenir (savoir combien d'éléments plus petits et plus grands sont là).

  Cette propriété globale est plus coûteuse à maintenir (insertion log n), mais donne des recherches plus puissantes (recherche log n).

• Les tas conservent une propriété locale entre le parent et les enfants directs (parent> enfants).

  Le nœud supérieur d'un tas est le grand élément, qui ne nécessite que des connaissances locales pour être maintenu (connaître votre parent).

Comparaison de BST vs Heap vs Hashmap:

• BST: peut être soit un raisonnable:

  • ensemble non ordonné (une structure qui détermine si un élément a déjà été inséré ou non). Mais hashmap a tendance à être meilleur en raison de l'insert amorti O (1).
  • trieuse. Mais le tas est généralement meilleur à cela, c'est pourquoi le tri en tas est beaucoup plus connu que le tri d'arbre

• tas: est juste une machine de tri. Il ne peut pas s'agir d'un ensemble non ordonné efficace, car vous ne pouvez rechercher que l'élément le plus petit / le plus grand rapidement.

• hash map: ne peut être qu'un ensemble non ordonné, pas une machine de tri efficace, car le hachage mélange n'importe quel ordre.

Liste à double lien

Une liste doublement liée peut être considérée comme un sous-ensemble du tas où le premier élément a la plus grande priorité, alors comparons-les ici également:

• insertion:
  • position:
    • liste doublement liée: l'élément inséré doit être le premier ou le dernier, car nous n'avons que des pointeurs vers ces éléments.
    • tas binaire: l'élément inséré peut se retrouver dans n'importe quelle position. Moins restrictif que la liste chaînée.
  • temps:
    • liste doublement chaînée: O(1)pire des cas puisque nous avons des pointeurs vers les éléments, et la mise à jour est vraiment simple
    • tas binaire: O(1)moyen, donc pire que la liste chaînée. Compromis pour avoir une position d'insertion plus générale.
• recherche: O(n)pour les deux

Un cas d'utilisation pour cela est lorsque la clé du tas est l'horodatage actuel: dans ce cas, les nouvelles entrées iront toujours au début de la liste. Ainsi, nous pouvons même oublier complètement l'horodatage exact et garder simplement la position dans la liste comme priorité.

Cela peut être utilisé pour implémenter un cache LRU . Tout comme pour les applications de tas comme Dijkstra , vous souhaiterez conserver une carte de hachage supplémentaire de la clé au nœud correspondant de la liste, pour trouver le nœud à mettre à jour rapidement.

Comparaison de différents BST équilibrés

Bien que les temps d'insertion et de recherche asymptotiques pour toutes les structures de données qui sont communément classées comme «BST équilibrées» que j'ai vues jusqu'à présent soient les mêmes, différents BBST ont des compromis différents. Je n'ai pas encore étudié complètement cela, mais il serait bon de résumer ces compromis ici:

• Arbre rouge-noir . Semble être le BBST le plus couramment utilisé à partir de 2019, par exemple, c'est celui utilisé par l'implémentation C ++ de GCC 8.3.0
• Arbre AVL . Semble être un peu plus équilibré que BST, il pourrait donc être préférable pour la latence de recherche, au prix de recherches légèrement plus chères. Le wiki résume: «Les arbres AVL sont souvent comparés aux arbres rouge-noir car les deux prennent en charge le même ensemble d’opérations et prennent [le même] temps pour les opérations de base. Pour les applications nécessitant une recherche intensive, les arbres AVL sont plus rapides que les arbres rouge-noir car ils sont plus strictement équilibrés. Semblables aux arbres rouge-noir, les arbres AVL sont équilibrés en hauteur. Les deux ne sont, en général, ni pondérés ni équilibrés en mu pour tout mu <1/2, c'est-à-dire que les nœuds frères peuvent avoir différents nombres de descendants. "
• WAVL . Le document original mentionne les avantages de cette version en termes de limites sur les opérations de rééquilibrage et de rotation.

Voir également

Question similaire sur CS: /cs/27860/whats-the-difference-between-a-binary-search-tree-and-a-binary-heap

Heap garantit simplement que les éléments des niveaux supérieurs sont plus grands (pour max-heap) ou plus petits (pour min-heap) que les éléments des niveaux inférieurs, alors que BST garantit l'ordre (de «gauche» à «droite»). Si vous voulez des éléments triés, utilisez BST.

Quand utiliser un tas et quand utiliser un BST

Heap est meilleur à findMin / findMax ( O(1)), tandis que BST est bon dans tous les find ( O(logN)). L'insert est O(logN)pour les deux structures. Si vous ne vous souciez que de findMin / findMax (par exemple lié à la priorité), optez pour le tas. Si vous voulez que tout soit trié, optez pour BST.

Les premières diapositives d' ici expliquent très clairement les choses.

Comme mentionné par d'autres, Heap peut faire findMin ou findMax dans O (1) mais pas les deux dans la même structure de données. Cependant, je ne suis pas d'accord pour dire que Heap est meilleur dans findMin / findMax. En fait, avec une légère modification, le BST peut faire les deux findMin et findMax en O (1).

Dans ce BST modifié, vous gardez une trace du nœud min et du nœud max chaque fois que vous effectuez une opération qui peut potentiellement modifier la structure des données. Par exemple, lors d'une opération d'insertion, vous pouvez vérifier si la valeur minimale est supérieure à la valeur nouvellement insérée, puis attribuer la valeur minimale au nœud nouvellement ajouté. La même technique peut être appliquée sur la valeur max. Par conséquent, ce BST contient ces informations que vous pouvez les récupérer dans O (1). (identique au tas binaire)

Dans ce BST (Balanced BST), lorsque vous pop minou pop max, la valeur min suivante à affecter est le successeur du nœud min, tandis que la valeur max suivante à affecter est le prédécesseur du nœud max. Ainsi, il fonctionne en O (1). Cependant, nous devons rééquilibrer l'arbre, donc il fonctionnera toujours O (log n). (identique au tas binaire)

Je serais intéressé d'entendre votre pensée dans le commentaire ci-dessous. Merci :)

Mettre à jour

Référence croisée à une question similaire Pouvons-nous utiliser un arbre de recherche binaire pour simuler une opération de tas? pour plus de discussion sur la simulation de Heap à l'aide de BST.

Un arbre de recherche binaire utilise la définition: que pour chaque nœud, le nœud à gauche de celui-ci a une valeur inférieure (clé) et le nœud à droite de celui-ci a une valeur plus grande (clé).

Où comme tas, étant une implémentation d'un arbre binaire utilise la définition suivante:

Si A et B sont des nœuds, où B est le nœud enfant de A, alors la valeur (clé) de A doit être supérieure ou égale à la valeur (clé) de B, c'est-à-dire clé (A) ≥ clé (B ).

http://wiki.answers.com/Q/Difference_between_binary_search_tree_and_heap_tree

J'ai posé la même question aujourd'hui pour mon examen et j'ai bien compris. sourire ... :)

Une autre utilisation de BST sur Heap; en raison d'une différence importante:

• trouver le successeur et le prédécesseur dans un BST prendra du temps O (h). (O (logn) dans BST équilibré)
• tandis que dans Heap, il faudrait un temps O (n) pour trouver le successeur ou le prédécesseur d'un élément.

Utilisation de BST sur un tas : Maintenant, disons que nous utilisons une structure de données pour stocker l'heure d'atterrissage des vols. Nous ne pouvons pas programmer un vol pour atterrir si la différence d'heures d'atterrissage est inférieure à «d». Et supposons que de nombreux vols ont été programmés pour atterrir dans une structure de données (BST ou Heap).

Maintenant, nous voulons programmer un autre vol qui atterrira à t . Par conséquent, nous devons calculer la différence de t avec son successeur et son prédécesseur (devrait être> d). Ainsi, nous aurons besoin d'un BST pour cela, qui le fait rapidement c'est- à- dire en O (logn) s'il est équilibré.

Édité:

Le tri BST prend O (n) temps pour imprimer les éléments dans l'ordre trié (traversée Inorder), tandis que Heap peut le faire en O (n logn). Heap extrait l'élément min et re-tasifie le tableau, ce qui lui fait faire le tri en temps O (n logn).

Insérer tous les n éléments d'un tableau dans BST prend O (n logn). n éléments d'un tableau peuvent être insérés dans un tas en temps O (n). Ce qui donne à tas un avantage certain

Heap garantit simplement que les éléments des niveaux supérieurs sont plus grands (pour max-heap) ou plus petits (pour min-heap) que les éléments de niveaux inférieurs

J'adore la réponse ci-dessus et mettre mon commentaire juste plus spécifique à mon besoin et à mon utilisation. J'ai dû obtenir la liste des n emplacements pour trouver la distance entre chaque emplacement et un point spécifique, par exemple (0,0), puis renvoyer les emplacements am ayant une distance plus petite. J'ai utilisé Priority Queue qui est Heap. Pour trouver les distances et mettre en tas, il m'a fallu n (log (n)) n-locations log (n) chaque insertion. Ensuite, pour obtenir m avec les distances les plus courtes, il a fallu m (log (n)) m-locations log (n) suppressions d'accumulation.

J'aurais dû faire cela avec BST, cela m'aurait fallu n (n) dans le pire des cas (disons que la première valeur est très petite et que toutes les autres viennent séquentiellement de plus en plus longtemps et que l'arbre s'étend à l'enfant droit uniquement ou à l'enfant gauche en cas de plus petit et plus petit. Le min aurait pris du temps O (1) mais encore une fois j'ai dû équilibrer. Donc, à partir de ma situation et de toutes les réponses ci-dessus, ce que j'ai obtenu, c'est quand vous êtes seulement après les valeurs à la base de priorité min ou max aller pour le tas.