Приоритетная очередь удаляет сложное время

Какова сложность (big-oh) для функции remove() в классе Priority Queue в Java? Я ничего не могу найти где-нибудь, я думаю, что это O (n), учитывая, что вы должны найти элемент, прежде чем удалить его, а затем перетасовать дерево. но я видел других, которые не согласны и думают, что это O (logn). Любые идеи?

Ответы

Ответ 1

Сложность для удаления - O (N), так как сложность для содержит O (N) (в классе очереди приоритетов java)

В одном случае это может быть сделано O (logN) в вашей собственной. Приоритетная реализация Queue предназначена для поддержки вспомогательной структуры данных, такой как HashMap, которая поддерживает сопоставления из значения в очереди приоритетов в свою позицию в очереди. Таким образом, в любой момент времени вы знаете позицию индекса любой ценности.

Обратите внимание, что эта модификация не влияет на время работы любой из существующих операций - вам нужно будет только обновлять сопоставления во время операций heapify.

Ответ 2

Путаница на самом деле вызвана вашей функцией "удалить". В java есть две функции удаления.

  • remove() → Чтобы удалить головку/корень, требуется время O (logN).

  • remove (Object o) → Это удаление произвольного объекта. Поиск этого объекта занимает время O (N), и для его удаления требуется время O (logN).

Ответ 3

Согласно документации Oracle: "Замечание по реализации: эта реализация обеспечивает O (log (n)) время для методов очереди и деоклирования (предложение, опрос, удалить() и добавить); линейное время для (Object) и содержит (Object) методы, а также постоянное время для методов поиска (peek, element и size).

Ссылка на Oracle Doc