Heap vs arbre de recherche binaire (BST)

169

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?

kc3
la source
13
Cette question semble hors sujet car elle concerne l'informatique et doit être posée sur cs.stackexchange.com
Flux du
3
@Flow, il y a été demandé à: cs.stackexchange.com/questions/27860/…
Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功
3
J'ai l'impression que cela concerne à la fois l'échange de pile et le débordement de pile. Donc l'avoir ici, c'est bien
Azizbro

Réponses:

191

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:

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:

entrez la description de l'image ici

  • 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.

entrez la description de l'image ici

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

Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功
la source
4
I + 1ed, mais le "papier" justifiant l'insertion moyenne du tas binaire O (1) est maintenant un lien mort, et les "slides" indiquent simplement la revendication sans preuve. Je pense également que cela aiderait à clarifier que "cas moyen" signifie ici la moyenne en supposant que les valeurs insérées proviennent d'une distribution particulière , donc je ne suis pas sûr de savoir comment "tueur" cette fonctionnalité est vraiment.
j_random_hacker
3
BST et BST équilibré semblent être utilisés de manière interchangeable. Il convient de préciser que la réponse fait référence à une BST équilibrée pour éviter toute confusion.
gkalpak
2
@Bulat Je pense que nous nous écartons un peu, mais si nous voulons à la fois max et min en même temps, nous pourrions rencontrer des problèmes avec le maintien de deux tas si nous ne faisons pas attention - stackoverflow.com/a/1098454/7154924 . Il est probablement préférable d'utiliser un tas max-min (dû à Atkinson et al.), Qui est spécialement conçu à cet effet.
flow2k
1
@CiroSantilli 新疆 改造 中心 六四 事件 法轮功: Je ne comprends pas pourquoi l'opération de suppression d'un tas binaire est O (log n). Cela ne fonctionne que si vous avez un pointeur vers l'élément dans le tas, mais dans la plupart des cas d'utilisation, vous avez la clé et vous devez d'abord trouver l'élément qui prend O (n).
Ricola
5
l'insertion de tas est log (n) pas o (1)
Bobo
78

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.

Code de Dante May
la source
8
"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,…" - le tas n'applique pas cela par niveau , mais seulement dans parent – ​​enfant- Chaînes. [1, 5, 9, 7, 15, 10, 11]représente un min-tas valide, mais 7le niveau 3 est plus petit que 9le niveau 2. Pour une visualisation, voir par exemple les éléments 25et 19dans l'exemple d'image Wikipedia pour les tas . (Notez également que les relations d'inégalité entre les éléments ne sont pas strictes, car les éléments ne sont pas nécessairement uniques.)
Daniel Andersson
Désolé pour l'entrée tardive, mais je veux juste obtenir des précisions. Si le tas binaire est trié, le pire des cas pour la recherche serait le log n correct. Donc, dans ce cas, les tas binaires sont mieux triés que les arbres de recherche binaires (BST rouge-noir). Merci
Krishna
50

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.

xysun
la source
3
Alors que l'insertion est logarithmique pour les deux dans le pire des cas, l'insertion moyenne du tas prend un temps constant. (Étant donné que la plupart des éléments existants sont en bas, dans la plupart des cas, un nouvel élément n'aura qu'à remonter d'un ou deux niveaux, voire pas du tout.)
johncip
1
@xysun Je pense que BST est meilleur dans findMin & findMax stackoverflow.com/a/27074221/764592
Yeo
2
@Yeo: Heap est meilleur pour findMin XOR FindMax. Si vous avez besoin des deux , alors BST est meilleur.
Mooing Duck
1
Je pense que c'est juste une idée fausse courante. Un arbre binaire peut être facilement modifié pour trouver min et max comme indiqué par Yeo. Il s'agit en fait d'une restriction du tas: la seule recherche efficace est min ou max. Le véritable avantage du tas est une insertion moyenne O (1) comme je l'explique: stackoverflow.com/a/29548834/895245
Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功
1
La réponse de Ciro Santilli est bien meilleure: stackoverflow.com/a/29548834/2873507
Vic Seedoubleyew
9

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.

Yeo
la source
Pourquoi n'êtes-vous pas d'accord? pourriez-vous partager votre pensée ci-dessous?
Yeo
Vous pouvez certainement stocker la valeur maximale et / ou minimale d'un BST, mais que se passe-t-il si vous voulez le faire apparaître? Vous devez rechercher l'arborescence pour le supprimer, puis rechercher à nouveau le nouveau max / min, qui sont tous deux des opérations O (log n). C'est le même ordre que les insertions et les suppressions dans un tas de priorité, avec une constante pire.
Justin
@JustinLardinois Désolé, j'ai oublié de le souligner dans ma réponse. Dans BST, lorsque vous faites pop min, la prochaine valeur min à affecter est le successeur du nœud min. et si vous sautez le max, la prochaine valeur max à affecter est le prédécesseur du noeud max. Ainsi, il fonctionne toujours en O (1).
Yeo
Correction: pour popMinou popMaxce n'est pas O (1), mais c'est O (log n) car il doit s'agir d'un Balanced BST qui doit être rééquilibré à chaque opération de suppression. Par conséquent, c'est la même chose que le tas binaire popMinou popMaxqui exécute O (log n)
Yeo
2
Vous pouvez obtenir le premier min / max, mais obtenir kth min / max reviendrait à la complexité BST normale.
Chaos
3

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 ... :)

Yevgraf Andreyevich Zhivago
la source
"tas, étant une implémentation d'un arbre binaire" - soulignant simplement qu'un tas est une sorte d'arbre binaire, pas une sorte de BST
Saad
3

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).

CODError
la source
1
Oui. Cela va de la séquence non triée à la séquence triée. O (n) temps de traversée en ordre d'un BST, ce qui donne une séquence triée Dans Heaps, vous extrayez l'élément min, puis re-heapify en temps O (log n). SO, il faudra O (n logn) pour extraire n éléments. Et cela vous laissera avec une séquence triée.
CODError
from unsorted to sorted sequence. O(n) time for inorder traversal of a BST, which gives sorted sequence.Eh bien, de la séquence non triée au BST, je ne connais pas de méthode basée sur une comparaison clé avec moins de temps O (n logn), qui domine la BST à la partie de séquence. (Alors qu'il existe une construction en tas O (n).). Je considérerais qu'il est juste (si inutile) d'indiquer que les tas sont proches de l'absence de tri et que les BST sont triés.
greybeard
Ce que j'essaie d'expliquer ici, c'est que si vous avez un BST et aussi un tas de n éléments => alors tous les éléments pourraient être imprimés dans un ordre trié à partir des deux structures de données et BST peut le faire en temps O (n) (traversée en ordre ), tandis que Heap prendrait du temps O (n logn). Je ne comprends pas ce que vous essayez de dire ici. Comment dites-vous que BST vous donnera une séquence triée en O (n logn).
CODError
Je pense que vous considérez également le temps nécessaire pour construire un BST et un Heap. Mais je suppose que vous l'avez déjà, que vous l'avez construit au fil du temps et que vous voulez maintenant obtenir le résultat trié. Je ne comprends pas votre point?
CODError
1
Modifié ... J'espère que vous êtes satisfait maintenant; p et donnez +1 si c'est correct.
CODError
1

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

AMR
la source
0

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.

Sahib Khan
la source