java.util.PriorityQueue разрешает Comparator для передачи во время разработки. При вставке элементы упорядочиваются в соответствии с приоритетом, заданным компаратором.
Что происходит, когда приоритет элемента изменяется после его вставки? Когда PriorityQueue переупорядочивает элементы? Можно ли опросить элемент, который на самом деле не имеет минимального приоритета?
Существуют ли хорошие реализации очереди приоритетов, позволяющие эффективно обновлять приоритеты?
Вы должны удалить элемент, изменить его и снова вставить, так как упорядочение происходит при его вставке. Хотя он включает в себя несколько шагов, он эффективен и может быть достаточно хорош. (Я только что заметил комментарий об удалении O (n).)
Одна проблема заключается в том, что он также изменит порядок, когда вы удалите элемент, что является излишним, если вы просто собираетесь повторно вставить его через мгновение. Если вы реализуете свою очередь приоритетов с нуля, у вас может быть функция update(), пропускающая этот шаг, но расширение класса Java не будет работать, поскольку вы по-прежнему ограничены функциями remove() и add(), предоставляемыми базой.
Я бы ожидал, что PriorityQueue не будет переупорядочивать вещи, и он может сильно запутаться, если попытается выполнить бинарный поиск, чтобы найти правильное место для размещения любых новых записей.
Вообще говоря, я ожидаю, что изменение приоритета чего-либо, уже находящегося в очереди, будет плохой идеей, точно так же, как изменение значений, составляющих ключ в хеш-таблице.
