Как получить минимальный элемент из приоритетной очереди после изменения содержимого очереди
Я пытался реализовать алгоритм Дейкстры, используя priority queue в Java.. К сожалению, он возвращал неправильные результаты... Я разыскал проблему. Вот проблема. После вставки весов узлов в очередь, я изменяю вес этих узлов, но когда я пытаюсь удалить элемент из очереди приоритетов, он возвращает исторический минимум (минимум во время вставки).remove() не знает, что приоритетная очередь была изменена.. Любая помощь будет принята с благодарностью... Спасибо!
Примечание: я могу добавить исходный код, если требуется
3 ответа
Стандартные интерфейсы не обеспечивают возможность обновления. Вы используете пользовательский тип, который реализует это. Это потому, что, как указано в сообщении SO под названием " Обновление Java PriorityQueue, когда его элементы меняют приоритет":
Вы должны удалить и повторно вставить, поскольку очередь работает, помещая новые элементы в соответствующее положение, когда они вставляются.
Как это влияет на вас, обсуждается в посте SO " Изменение порядка очередей Java при редактировании элементов":
Очередь с приоритетом не обрабатывает все элементы всякий раз, когда элемент добавляется или удаляется.... Это будет слишком дорого. PriorityQueue не предлагает API для информирования его об измененном узле, так как это потребовало бы от него обеспечения эффективного поиска узла, который не поддерживается его базовым алгоритмом.
Приведенные выше посты предоставляют альтернативные методы для реализации алгоритма Дийсктра.
Пожалуйста, дай мне знать, если возникнут какие-либо вопросы!
Этот ТАК вопрос должен вам помочь. Недостаток PriorityQueue в Java состоит в том, что если изменяется значение вставленного элемента, очередь приоритетов не перестраивается для отражения нового порядка. Таким образом, вам придется удалить и повторно вставить изменяющиеся элементы, чтобы удовлетворить ваш вариант использования.
Так же, как ключи Mapэлементы, которые вы положили в PriorityQueue должен быть неизменным. Элемент, который вставлен в PriorityQueue сравнивается со всеми существующими элементами в PriorityQueue, Итак, если базовый элемент изменяется, ваш PriorityQueue скорее всего не сможет удержать инварианты.
Альтернативная структура данных, которую вы можете использовать, может быть TreeSet, remove операция по TreeSet является O(LG N).