Приоритетные очереди в Java

java.util.PriorityQueue позволяет Comparator, которое должно быть принято во время строительства. При вставке элементов они упорядочиваются в соответствии с приоритетом, указанным компаратором.

Что происходит, когда приоритет элемента изменяется после его вставки? Когда элементы PriorityQueue переупорядочивают? Возможно ли опросить элемент, который на самом деле не имеет минимального приоритета?

Есть ли хорошие реализации очереди приоритетов, которые позволяют эффективно обновлять приоритет?

Ответ 1

Вы должны удалить элемент, изменить его и повторно вставить, так как упорядочение происходит, когда оно вставлено. Хотя он включает в себя несколько шагов, он ~~эффективен~~ может быть достаточно хорошим. (Я только заметил комментарий об удалении: O (n).)

Одна из проблем заключается в том, что она также будет повторно упорядочена, когда вы удалите элемент, который является избыточным, если вы просто собираетесь его повторно вставить позже. Если вы реализуете свою собственную очередь приоритетов с нуля, вы можете иметь update(), который пропускает этот шаг, но расширение класса Java не будет работать, поскольку вы все еще ограничены функциями remove() и add(), предоставляемыми базой.

Ответ 2

Я бы ожидал, что PriorityQueue не изменит порядок вещей, и он может сильно запутаться, если попытается выполнить двоичный поиск, чтобы найти нужное место для размещения каких-либо новых записей.

Вообще говоря, я ожидаю, что изменение приоритета того, что уже находится в очереди, будет плохой идеей, подобно изменению значений, составляющих ключ в хеш-таблице.