Quand dois-je utiliser un TreeMap sur une PriorityQueue et vice versa?
semble qu'ils vous permettent à la fois de récupérer le minimum, qui est ce dont j'ai besoin pour l'algorithme de Prim, et me forcer à enlever et réinsérer une clé pour mettre à jour sa valeur. Y a-t-il un avantage à utiliser l'un par rapport à l'autre, non seulement pour cet exemple, mais de manière générale?
7 réponses
en général, il est moins difficile de suivre seulement l'élément minimum, en utilisant un tas.
un arbre est plus organisé, et il nécessite plus de calcul pour maintenir cette organisation. Mais si vous avez besoin d'accéder à n'importe quelle clé, et pas seulement le minimum, un tas ne suffira pas, et le dépassement supplémentaire de l'arbre est justifié.
totalement d'accord avec Erickson sur le fait que la file d'attente prioritaire ne vous donne que l'élément minimum/maximum.
en outre, parce que la file d'attente de priorité est moins puissante dans le maintien de l'ordre total des données, elle a l'avantage dans certains cas spéciaux. Si vous voulez suivre les plus grands M éléments dans un tableau de N , la complexité du temps serait O(N*LogM) et la complexité de l'espace serait O(M) . Mais si vous le faites dans une carte, le temps la complexité est O(N*logN) et l'espace O(N) . C'est assez fondamental alors que nous devons utiliser la file d'attente de priorité dans certains cas par exemple M est juste une constante comme 10.
il y a 2 différences que je voudrais souligner (et cela pourrait être plus pertinent pour différence entre PriorityQueue et TreeSet en Java? puisque cette question est considérée comme un dup de cette question).
(1) PriorityQueue peut avoir des doublons, où, comme TreeSet ne peut PAS avoir de dup. Donc dans Treeset, si votre comparateur considère que 2 éléments sont égaux, TreeSet gardera seulement un de ces 2 éléments et jettera l'autre.
(2) TreeSet iterator traverse la collection dans un ordre trié, alors que PriorityQueue iterator ne traverse pas dans l'ordre trié. Pour PriorityQueue si vous voulez obtenir les articles dans l'ordre, vous devez détruire la file d'attente en appelant remove() à plusieurs reprises.
je suppose que la discussion est limitée à L'implémentation de Java de ces structures de données.
Règle du pouce, c'est:
TreeMap maintient tous les éléments d'ordre. (Donc, intuitivement, il faut du temps pour le construire)
PriorityQueue seulement quarantaine min ou max. C'est moins cher mais moins puissante.
l'une des différences est que remove(Object) et contains(Object) sont linéaires O(N) dans un tas normal basé PriorityQueue (comme Oracle), mais O(log(N)) pour un arbre/carte.
donc si vous avez un grand nombre d'éléments et faites beaucoup de remove(Object) ou contains(Object), alors un TreeSet/Map peut être plus rapide.
tout dépend de ce que vous voulez atteindre. Voici les principaux points à considérer avant de choisir l'un plutôt que l'autre.
- PriorityQueue Allows Duplicate(I. e avec la même priorité) alors que TreeMap ne le fait pas.
- la Complexité de PriorityQueue est O(n)(quand est-augmente sa taille), alors que celle de TreeMap est O(logn)(comme il est basé sur le Rouge Noir de l'Arbre)
- PriorityQueue est basé sur Array alors que dans TreeMap les noeuds sont liés à l'un l'autre, ainsi contient méthode de PriorityQueue prendrait O(n) temps tandis que TreeMap prendrait O(logn) temps.
cela dépend de la façon dont vous mettez en œuvre votre File D'attente prioritaire. Selon le livre de Cormen 2nd ed le résultat le plus rapide est avec un tas de Fibonacci.