Очередь приоритетов убирает время сложности
Какова сложность (биг-о-о) для remove() функция в классе очереди приоритетов в Java? Я нигде не могу найти ничего задокументированного, я думаю, что это O(n), учитывая, что вы должны найти элемент, прежде чем удалить его, а затем переставить дерево. но я видел других, которые не согласны и думают, что это O(logn). Есть идеи?
4 ответа
Путаница на самом деле вызвана вашей функцией "удалить". В Java есть две функции удаления.
remove () -> Это чтобы удалить head/root, это занимает O(logN) время.
remove (Object o) -> Это для удаления произвольного объекта. Нахождение этого объекта занимает O(N) времени, а его удаление занимает O(logN) времени.
Сложность удаления - O(N), так как сложность содержимого - O(N) (в классе очередей с приоритетами Java)
Одним из способов сделать это O(logN) в вашей собственной реализации очереди приоритетов является поддержание вспомогательной структуры данных, такой как HashMap, которая поддерживает сопоставления от значения в приоритетной очереди до его положения в очереди. Таким образом, в любой момент времени вы будете знать позицию индекса любого значения.
Обратите внимание, что это изменение не влияет на время выполнения какой-либо из существующих операций - вам нужно будет только обновить отображения во время операций heapify.
Согласно документации Oracle: "Замечание по реализации: эта реализация обеспечивает время O (log (n)) для методов выделения и удаления (предложение, опрос, удаление () и добавление); линейное время для удаления (Объект) и содержит (Объект").) методы и постоянное время для методов поиска (peek, element и size)."
Пожалуйста, проверьте: http://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html
«эта реализация обеспечивает время O (log (n)) для методов постановки и удаления (предложение, опрос, удаление () и добавление); линейное время для методов remove (Object) и содержит (Object)»
Таким образом, для poll () и remove () это 'log(N) Но для remove (object) это log(N)