Почему в Java Priority Queue отсутствует метод Change Priority?
Мне было интересно, почему Java Priority Queue не поддерживает ChangePriority. Я где-то читал (без подробностей), что удаление ChangePriority позволяет использовать более эффективную реализацию, но я понятия не имею, как это возможно - двоичная куча кажется довольно простой / эффективной структурой данных - не вижу места для улучшения. Другая подсказка может заключаться в том, что может потребоваться неудобный интерфейс для указания PQ, какой элемент (предположительно, позиция в куче) меняет свой приоритет, но все же я новичок в Java, чтобы прийти к выводу.
Редактировать: Почему это не может быть бессмысленным вопросом? Если вы новичок в Java (особенно из C/C++ фона), вы начинаете задумываться о таких вещах, как, куда делись все указатели, или как я могу реализовать Dijkstra в Java и т. Д.
На первый вопрос отвечали много раз, на второй, насколько я понимаю, не было простого ответа. Можно ожидать, что в таком языке, как Java, у вас есть все обычные инструменты программирования, готовые к работе, встроенные в красивую оболочку класса. Но неожиданно вам приходится самостоятельно реализовывать метод PQ с уменьшением ключа, что, возможно, более неудобно в Java, чем в C/C++. В этом вопросе я не спрашиваю, как реализовать Дейкстру (на этот вопрос приятно ответили в какой-то другой ветке). Там все еще может быть много приложений PQ, которые не могут быть отсортированы без использования метода "ключ уменьшения / prio", например. если есть гораздо больше приоритетных обновлений, чем элементы в PQ. В Дейкстре есть максимум V
Таким образом, можно ожидать, что есть некоторые серьезные причины, по которым в Java PQ отсутствует приоритет изменения. Причины, вероятно, интересны сами по себе, независимо от реального интерфейса PQ в Java.
2 ответа
Я подозреваю, что выбор дизайна, потому что его Queue, Основные операции очереди - это постановка в очередь и извлечение из очереди. Priority Queue отличается тем, что как часть операции enqueue он позволяет элементу иметь приоритет над другими. Наиболее Queue реализации не позволяют манипулировать элементами после их установки, хотя некоторые предоставляют peek возможностей. Так как наш тип данных является очередью, я не должен "связываться" с внутренним устройством, и меня это не должно волновать. Если я использую очередь, я в основном хочу поведение First In First Out. Очередь
При этом, как вы могли бы достичь желаемого поведения? Я бы порекомендовал TreeMap, Это дает вам функциональность, похожую на очередь, я могу получить первый или последний элемент через firstKey() или же lastKey(), в то же время предоставляя искусственный заказ через мой собственный Comparator интерфейс, а также доступ к записям через Keyхоть и твой Key Реализация должна обеспечивать как уникальный идентификатор, так и порядок сортировки.
Хотя я не могу быть уверен, почему методы изменения приоритета не были PriorityQueueможно заметить, что когда приоритет объекта в PriorityQueue изменения, вы можете просто удалить и заново вставить объект.
Это поведение PriorityQueue существует, потому что всякий раз, когда новый объект вставляется в очередь, он помещается в соответствующую позицию (на основе компаратора объекта). Это хорошо работает, потому что каждый раз, когда что-то извлекается из очереди, не требуется повторных вычислений для поиска элемента с приоритетом min / max. Это накладывает ограничение на то, что приоритет объекта не может быть изменен после того, как он был вставлен в очередь.
Это правда, что удаление и повторная вставка объекта происходит медленнее, и видно, что общая сложность времени выполнения вашего кода останется прежней. Тем не менее, если вы заинтересованы в рассмотрении пользовательских реализаций Java в Приоритетной очереди, это может быть хорошим местом для начала - http://algs4.cs.princeton.edu/24pq/IndexMinPQ.java.html