Wenn ich den höchsten Eintrag in log(n) time in Java TreeSet entfernen möchte, verwende ich treeSet.pollFirst() - was ist das Äquivalent für Scala mutable.TreeSet class?
Wie auch immer, ich möchte wirklich eine haufenähnliche Datenstruktur der Prioritätswarteschlange, die mir removeMax , add und updatePriority in logarithmischer Zeit erlaubt. Ich habe mir die Scala Collections Bibliothek angeschaut und bin verwirrt - während mutable.PriorityQueue mich deque (dh removeMax ) in logarithmischer Zeit erlaubt - es bietet keine Möglichkeit die Priorität in der Log-Zeit zu aktualisieren (ich müsste hacky scannen und entfernen Element und neu hinzufügen in linearer Zeit). In ähnlicher Weise würde mutable.TreeSet die Priorität in logarithmischer Zeit aktualisieren (durch hackiges Löschen und erneutes Hinzufügen), aber es hat keine Operation removeMax (d. H.% Co_de%). Welchen Sammelbehälter soll ich verwenden? Bitte verweisen Sie mich nicht auf externe Abhängigkeiten.
Sie können die Methoden head und last in immutable.TreeSet verwenden, die O(log n) sind.
Dieselben Methoden existieren in mutable.TreeSet , wurden aber nicht überschrieben, um eine bessere Effizienz und amortisierte Zeit zu erreichen (in Scala 2.10). Die Methode head ist logarithmisch, kann jedoch einen Iterator instanziieren. Die last -Methode wird sie tatsächlich durchlaufen und eine lineare Komplexität aufweisen. Die gute Nachricht ist, dass Sie mit einer benutzerdefinierten Ordering steuern können, was am kleinsten oder am größten ist - und es leicht von einem vorhandenen Ordering erhalten, indem Sie Ordering.reverse aufrufen.
Wenn Sie dieses Element entfernen müssen, verwenden Sie einfach -= . Sie können Ihre eigene implizite Wertklasse erstellen, um die Methode pollFirst in der Baumstruktur zu übernehmen.
Keine Antwort, nur ein Vorschlag :) Denken Sie daran, dass Sie von scala auf Java-Bibliotheken zugreifen können (naja, wenn Sie die JVM kompilieren :). Wenn Java's TreeSet für Sie arbeitet, verwenden Sie es:)
Sie können auch Ihre Anforderungen klären; Was wären die Parameter Ihrer updatePriority-Methode? Wessen Priorität versuchst du zu aktualisieren?
Tags und Links scala java priority-queue scala-collections treeset