Kolejki priorytetowe w Javie

Question

java.util.PriorityQueue pozwala na przekazanie Comparator w czasie budowy. Podczas wstawiania elementów są one sortowane zgodnie z priorytetem określonym przez komparator.

Co się stanie, gdy priorytet elementu zmieni się po włożeniu? Kiedy następuje zmiana kolejności elementów? Czy możliwe jest odpytywanie elementu, który w rzeczywistości nie ma minimalnego priorytetu?

Czy istnieją dobre wdrożenia kolejki priorytetów, które umożliwiają wydajne aktualizacje priorytetów?

Answer 1

Powinieneś usunąć element, zmienić go i ponownie włożyć, ponieważ zamawianie następuje po włożeniu. Chociaż wymaga to kilku etapów, to jest efektywny. może być wystarczająco dobry. (Właśnie zauważyłem, że komentarz o usunięciu to O (n).)

Jednym z problemów jest to, że będzie on również zmieniać kolejność po usunięciu elementu, który jest zbędny, jeśli zamierzasz go ponownie wstawić chwilę później. Jeśli zaimplementujesz własną kolejkę priorytetów od podstaw, możesz mieć aktualizację(), która pominie ten krok, ale rozszerzenie klasy Java nie będzie działać, ponieważ nadal jesteś ograniczony do remove() i add() dostarczonych przez bazę.

Answer 2

bym oczekiwać się PriorityQueue aby nie zmienić kolejność rzeczy - a to może się bardzo mylić, jeśli próbuje zrobić binarne wyszukiwania, aby znaleźć odpowiednie miejsce do wprowadzenia żadnych nowych wpisów.

Ogólnie rzecz biorąc, oczekiwałbym zmiany priorytetu czegoś już w kolejce na zły pomysł, podobnie jak zmiana wartości składających się na klucz w tabeli mieszania.