Java Prioritätswarteschlange

Question

Java Prioritätswarteschlange eine Datenstruktur mit O(log n) Komplexität ist für put (insertion) und O(log n) für poll (Retrieval und Entfernung des min-Elements).

C ++ STL multimap hat die gleiche Funktionalität, aber O(1) Komplexität für den Abruf und Entfernen des Elements min (beginnen und löschen). Gibt es ein Äquivalent in Java?

Answer 1

Google Sammlungen eine Multimap Implementierung zur Verfügung stellt. Insbesondere kann ein TreeMultimap Komparatoren basierend auf entweder Schlüssel, Werte oder beide sortieren verwenden.

Answer 2

Versuchen Sie, die Apache Commons Sammlungen .

MultiHashMap und MultiValueMap (von dieser Seite verlinkt ist) implementieren tatsächlich die Schnittstelle.

Es gibt tatsächlich eine Priority Queue auch drin, aber es ist für die Pufferpaket .

Answer 3

Als erstes würde ich prüfen, dass C ++ 's multimap tut eigentlich O geben (1) für Entfernen das min-Element. Die häufigsten Strukturen für sotred Karten / Prioritäts-Warteschlangen sind Baumstrukturen in denen Abfragen die min Element O (1) die Komplexität, aber Entfernen es ist O (log n).

Das heißt, glaube ich, dass eine Sprungliste (wie von Java implementiert ConcurrentSkipListMap ) könnte geben Sie O (1) zur Entfernung des Mindest Element, aber ich ist nicht absolut sicher. Eines der Probleme bei der Leistung von ConcurrentSkipListMap Beurteilung ist, dass Traversal operations „aufzuräumen“ Marker von früheren Löschungen links. So ist die Komplexität einer Operation kann tatsächlich davon abhängen, was die vorherigen Operationen waren. (Auf der anderen Seite, zu einem gewissen Grad, das ist wahr von so ziemlich jedem Algorithmus: ob einige Daten in der CPU-Cache kann davon abhängen, ob eine vorherige Operation ihn dort ...)

P. S. Vergessen zu sagen: Blick auf ConcurrentSkipListMap.pollFirstEntry ()

.

Answer 4

std:multimap wird eine Baumstruktur, was bedeutet, dass hinzufügen und entfernen wird zusammen sein O (log n).