Java PriorityQueue wird aktualisiert, wenn die Elemente ihre Priorität ändern

Question

Ich versuche eine PriorityQueue zu verwenden, um Objekte mit einer Comparator zu bestellen.

Dies kann leicht erreicht werden, aber die Variablen der Objektklasse (mit der der Komparator die Priorität berechnet) können sich nach dem ersten Einfügen ändern. Die meisten Leute haben die einfache Lösung vorgeschlagen, das Objekt zu entfernen, die Werte zu aktualisieren und sie erneut einzufügen, da dies der Fall ist, wenn der Komparator der Prioritätswarteschlange in Aktion gesetzt wird.

Gibt es eine bessere Möglichkeit, als nur eine Wrapper-Klasse um die PriorityQueue zu erstellen, um dies zu tun?

Answer 1

Sie müssen entfernen und neu einfügen, wie die Warteschlange funktioniert, indem neue Elemente an der richtigen Stelle eingefügt werden, wenn sie eingefügt werden. Dies ist viel schneller als die Alternative, das Element mit der höchsten Priorität jedes Mal zu finden, wenn Sie die Warteschlange verlassen. Der Nachteil ist, dass Sie die Priorität nicht ändern können, nachdem das Element eingefügt wurde. Eine TreeMap hat dieselbe Einschränkung (wie eine HashMap, die auch bricht, wenn sich der Hashcode ihrer Elemente nach dem Einfügen ändert).

Wenn Sie einen Wrapper schreiben möchten, können Sie den Vergleichscode von der Warteschlange in die Warteschlange verschieben. Sie müssten nicht mehr in der Warteschleife sortieren (weil die Reihenfolge, die sie erstellt, nicht zuverlässig ist, wenn Sie Änderungen zulassen).

Aber das wird schlechter laufen, und Sie möchten in der Warteschlange synchronisieren, wenn Sie eine der Prioritäten ändern. Da Sie beim Aktualisieren von Prioritäten Synchronisationscode hinzufügen müssen, können Sie auch einfach die Warteschlange aufheben und in die Warteschlange stellen (in beiden Fällen benötigen Sie den Verweis auf die Warteschlange).

Answer 2

Ich weiß nicht, ob es eine Java-Implementierung gibt, aber wenn Sie wichtige Werte ändern, können Sie einen Fibonnaci-Heap verwenden, der 0 (0) einen Schlüsselwert von 0 hat Eintrag in den Heap, anstatt O (log (n)) wie in einem normalen Heap.

Answer 3

Es hängt viel davon ab, ob Sie direkte Kontrolle über haben, wenn die Werte ändern.

Wenn Sie wissen, wann sich die Werte ändern, können Sie entweder entfernen und erneut einfügen (was in der Tat ziemlich teuer ist, da das Entfernen einen linearen Scan über den Heap erfordert!). Darüber hinaus können Sie für diese Situation eine UpdatableHeap-Struktur (nicht auf Lager Java) verwenden. Im Wesentlichen ist das ein Heap, der die Position von Elementen in einer Hashmap verfolgt. Wenn sich die Priorität eines Elements ändert, kann es auf diese Weise den Heap reparieren. Drittens können Sie nach einem Fibonacci-Heap suchen, der dasselbe tut.

Je nach Aktualisierungsrate funktioniert möglicherweise auch ein linearer Scan/Quicksort/QuickSelect. Insbesondere, wenn Sie viel mehr Updates als pull s haben, ist dies der Weg zu gehen. QuickSelect ist wahrscheinlich am besten, wenn Sie Stapel von Aktualisierungen und dann Stapel Pull-Operationen haben.