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

Question

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

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

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

Answer 1

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

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

Answer 2

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

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