Gibt es einen nicht zu komplizierten Weg, eine Prioritätswarteschlange mit zwei Kriterien zu implementieren? Die Warteschlange wird mit 2 Comparator s erstellt und stellt (neben add ) die Operationen poll1() und poll2() zur Verfügung, wobei jede das kleinste Element entsprechend dem entsprechenden Komparator entfernt und zurückgibt.
Beachten Sie, dass es mit diesen zwei Fragen .
Mein Anwendungsfall ist Branch and Bound Optimization . Das Expandieren des Kandidaten mit der besten Bindung ist nachweislich optimal, wenn Sie eine unbegrenzte Zeit erhalten. Vorausgesetzt, eine unbegrenzte Zeit ist nachweislich falsch.
Wenn man diese Strategie strikt befolgt, endet die Frist oft nicht. Ein einfaches Pflaster ist, die Suche zuerst auf eine Lösung zu richten und dann auf die beste gebundene Strategie umzuschalten. Dies ist eher unbefriedigend, da die erste gefundene Lösung eine beliebig niedrige Qualität haben kann.
Deshalb würde ich gerne die zwei Kriterien-Queue verwenden: In einem Schritt erweitern Sie den besten gebundenen Kandidaten und in einem anderen erweitern Sie den "am besten aussehenden" Kandidaten gemäß einiger Heuristiken.
Eine weitere mögliche Verwendung wäre die Pareto-Optimierung.
Das Ziel dieser Aufgabe wäre es hoffentlich, die gleichen amortizierten Laufzeiten für die Zielprioritätswarteschlange beizubehalten.
Diese Laufzeiten sind O(log n) für das Einfügen und Entfernen.
Pflegen Sie zwei Prioritätswarteschlangen mit jeweils einem eigenen Vergleicher. Pflegen Sie eine Karte der Zählungen der hinzugefügten Objekte. Wenn ein Objekt aus der Warteschlange entfernt wird, verringern Sie die Anzahl. Wenn das Objekt, das Sie aus der Warteschlange abfragen möchten, eine Zählung & lt; = 0 hat, dann rufen Sie ein anderes Element ab.
Die folgende Implementierung behält die Laufzeiten bei. Es hat O(log n) für das Einfügen und Entfernen amoritisiert. Da jedes Element zu jeder Warteschlange hinzugefügt und nur einmal aus jeder Warteschlange entfernt wird, muss es ein konstantes Vielfaches der Laufzeit einer einzelnen Warteschlange sein. Darüber hinaus hat die Karte Ein- und Ausblendzeiten von O(1) , was nicht zur Laufzeit von O(log n) für die Warteschlangen beiträgt.
Verwenden Sie zwei TreeSet s. Jeder Satz nimmt seinen respektierten Komparator und die Methode add() fügt jedem Satz den bereitgestellten Wert hinzu. poll1() würde den Wert first() in der ersten Menge erhalten und den Wert aus beiden Mengen entfernen. Ähnlich für poll2() .
add() , poll1() und poll2() haben Ο (log n ).
Es folgt eine Beispielimplementierung (die reale Sache benötigt wahrscheinlich mehr Fehlerprüfung und zusätzliche Methoden):
%Vor%Verwenden Sie zwei Prioritätswarteschlangen.
Eine Möglichkeit besteht darin, ein Element zum Löschen zu markieren, wenn es in der nächsten Umfrage als Nächstes angezeigt wird. Wenn die andere Warteschlange es sieht, überspringen Sie und gehen Sie zum nächsten. Ich bin mir nicht sicher, wie komplex das ist, aber es hängt von subtilen Fragen ab, wie viel länger ein Gegenstand in einer Schlange bleibt als der andere. Ich würde vorschlagen, für Ihre aktuelle Situation ein Profil zu erstellen.
Wenn Sie nur asymptotische Komplexität interessieren, würde ich mit @ jxhs Lösung gehen, die O(n) Speicher und garantierte Zeit O(log(n)) pro Operation verwendet (das ist das bestmögliche) und sehr wenig Kodierung benötigt.
Allerdings TreeSet wird gesichert von TreeMap und das verwendet TreeEntry für Einträge, und ein Eintrag dauert total 32B des Speichers plus 2 Bäume ergeben 64B des Speichers pro Element!
EDIT 2: Die alte Antwort war falsch, ich habe hier verschoben irgendjemand will es trotzdem sehen. Folgt (hoffentlich) korrekter Antwort.
Die Idee ist wirklich einfach. Lassen Sie uns 2 gewöhnliche Heaps haben, einer sortiert über den ersten Komparator, der andere sortiert über den zweiten Komparator. Und mit diesen zwei Indexierungs-Arrays, die die Elemente zwischen den Heaps verbinden.
Wenn sich das Element X beispielsweise an Position 2 in Heap 1 und an Position 8 in Heap 2 befindet, sehen die verknüpfenden Arrays folgendermaßen aus:
%Vor%Wenn Sie also ein Element in einem der Heaps bewegen, müssen Sie diese Arrays entsprechend aktualisieren.
Aber jetzt, wenn Sie Minimum von einem Haufen entfernen, wissen Sie, wo dieses Element im zweiten Haufen war, also können Sie es auch von dort entfernen.
Ich habe den vollständigen Code hier gepostet, diese Lösung benötigt nur 16B pro Element und war noch schneller Die @ jxh-Lösung in den Tests, die ich gemacht habe, aber ich habe einfache Arrays mit maximaler Kapazität anstelle einiger automatisch wachsenden Strukturen wie ArrayList verwendet.
Tags und Links java priority-queue