Javas priority queue ist eine Datenstruktur mit O(log n) Komplexität für Put (Einfügen) und O(log n) für Abfrage (Abruf und Entfernen des min-Elements).Java-Prioritätswarteschlange
C++ STL multimap hat die gleiche Funktionalität aber O(1) Komplexität für das Abrufen und Entfernen des min-Elements (beginnen und löschen). Gibt es eine Entsprechung in Java?
Google Collections bietet eine Multimap-Implementierung. Insbesondere kann ein TreeMultimap Komparatoren verwenden, um basierend auf Schlüsseln, Werten oder beiden zu sortieren.
Google Multimaps unterstützen nicht die Reihenfolge der Schlüssel, was scheint impliziert für C++ eins, oder? –
Ich habe meine Antwort aktualisiert, um speziell auf TreeMultimap beziehen – Mark
Versuchen Sie die Apache Commons Collections.
MultiHashMap und MultiValueMap (von dieser Seite aus verlinkt) implementieren die Schnittstelle tatsächlich.
Es ist auch eine Priority Queue drin, aber es ist zugunsten der buffer package abgeschrieben.
std:multimap wird eine Baumstruktur sein, was bedeutet, dass add und remove zusammen O (log n) sind.
hinzufügen und entfernen sind O (1) amortisiert. –
O (1) für eine Hash-Struktur. Aber für einen Baum? –
Zuerst würde ich überprüfen, dass C++ 's multimap tatsächlich O (1) für das min Element zu entfernen gibt. Die gebräuchlichsten Strukturen für sortenreine Karten/Prioritätswarteschlangen sind Baumstrukturen, in denen abgefragt wird. Das min-Element hat O (1) -Komplexität, aber entfernt es ist O (log n).
Das heißt, glaube ich, dass eine Sprungliste (als ConcurrentSkipListMap von Java implementiert) könnte geben Sie O (1) zur Entfernung des Mindest Element, aber ich bin mir nicht ganz sicher. Eines der Probleme bei der Beurteilung der Leistung von ConcurrentSkipListMap besteht darin, dass die Traversierungsoperationen Marker "aufräumen", die von vorherigen Löschungen übrig geblieben sind. So kann die Komplexität einer Operation tatsächlich davon abhängen, was die vorherigen Operationen waren. (Auf der anderen Seite, auf einer bestimmten Ebene gilt das für so ziemlich jeden Algorithmus: ob einige Daten im CPU-Cache sind, kann davon abhängen, ob eine vorherige Operation sie dorthin gebracht hat ...)
P.S. Vergessen zu sagen: siehe ConcurrentSkipListMap.pollFirstEntry().
multimap's Erase (Iterator x) ist konstant amortisiert, also ja, ist es. priority_queue's pop ist jedoch O (log N). –
Greg - wissen Sie, welche Struktur sie dafür verwenden? –
Können Sie bitte erklären, wie eine Warteschlange eine Multimap sein kann? Der erste hat einen Typparameter und der zweite hat zwei. –
Verwenden Void als zweiten Typparameter? –
Sie müssen einen benutzerdefinierten Operator