Получить доступ

Какая алгоритмическая сложность операций PriorityQueue (бинарной кучи)?

MiddleКоллекции
Коротко

offer и poll — O(log n) (просеивание вверх и вниз), peek — O(1) (корень), remove(Object) и contains — O(n) (линейный поиск).

  • Куча в массиве: дети узла i — 2i+1 и 2i+2
  • Построение из коллекции — O(n)
  • Конкурентный вариант — PriorityBlockingQueue

А ещё Топ-K за O(n log k): куча размера k

Так подсказку видит пользователь sotto на живом собеседовании — за пару секунд, пока вы думаете вслух.

Попробуйте сами

Двоичная куча: вставка и извлечение

Подробно

Куча хранится в массиве (дети узла i в 2i+1 и 2i+2). Вставка и снятие восстанавливают свойство кучи просеиванием — O(log n); корень (минимум по Comparable/Comparator) доступен за O(1) через peek. Для конкурентного варианта есть PriorityBlockingQueue.

Что хотят услышать

  • Сложность основных операций и почему.
  • Линейность remove и contains.

Частые ошибки

  • Думать, что poll ищет минимум линейно.
  • Считать peek дорогим.

Проверьте себя

Один верный вариант. Подумайте, потом откройте ответ.

Показать варианты и ответ
  • ✓offer и poll — O(log n) (просеивание вверх/вниз), peek — O(1)
  • ✗Все операции O(1)
  • ✗offer O(1), poll O(n) — линейный поиск минимума
  • ✗Все операции O(log n), включая peek

Что спросят дальше

  • Как устроено просеивание (sift up/down)?
  • Чем PriorityBlockingQueue отличается?

Разбор темы

Связанные вопросы

Закрытая бета

Подсказки на собеседовании — в реальном времени

sotto слышит вопрос интервьюера и показывает короткий ответ и план, как в блоке «Коротко». Оставьте контакт — пришлём доступ и промокод.

  • Промокод на 2 часа — сверх пробных 30 минут
  • Программа для Windows — скачать сразу, войти — через Яндекс ID или VK ID
  • Прямая связь с разработчиком: что улучшить — сделаем