File d'attente prioritaire Java

Question

file d'attente prioritaire de Java Java est une structure de données avec une complexité O (log n) pour put (insertion) et O (log n) pour une interrogation (extraction et suppression de l'élément min).

La

carte multimédia de la STL C ++ a la même fonctionnalité, mais le O ( 1) complexité pour la récupération et la suppression de l'élément min (begin et erase). Existe-t-il un équivalent en Java?

Answer 1

Google Collections fournit une implémentation multimap. TreeMultimap peut utiliser des comparateurs pour effectuer un tri basé sur des clés, des valeurs ou les deux.

Answer 2

Essayez le Collections Apache Commons .

MultiHashMap et MultiValueMap (liés à partir de cette page) implémentent réellement l'interface.

Il existe en fait un File d'attente prioritaire y aussi, mais il s’est déprécié au profit de package de tampon .

Answer 3

Tout d’abord, je vérifierais que la carte multiple de C ++ donne effectivement O (1) pour supprimer l’élément min. Les structures les plus courantes pour les files d'attente prioritaires / de correspondance sotred sont les arborescences dans lesquelles interrogeant l'élément min a une complexité de O (1), mais le supprimant il s'agit de O (log n).

Cela dit, je pense qu'une liste de sauts (telle que mise en œuvre par ConcurrentSkipListMap de Java) pourrait vous donner le contrôle O (1) pour la suppression de l'élément minimum, mais ' Je ne suis pas absolument sûr. L’un des problèmes rencontrés lors de l’évaluation des performances de ConcurrentSkipListMap réside dans le fait que les opérations de parcours "tidy up" marqueurs laissés par les suppressions précédentes. La complexité d’une opération peut donc dépendre des opérations précédentes. (D'un autre côté, à un certain niveau, c'est le cas de pratiquement tous les algorithmes: la présence de certaines données dans le cache du processeur peut dépendre du fait qu'une opération précédente l'ait mise là-bas ...)

P.S. Oubli de dire: consultez ConcurrentSkipListMap.pollFirstEntry () .

Answer 4

std: multimap sera une structure arborescente, ce qui signifie que tous les ajouts et les suppressions seront O (log n).