Какая алгоритмическая сложность операций PriorityQueue (бинарной кучи)?
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
Подробно
Куча хранится в массиве (дети узла i в 2i+1 и 2i+2). Вставка и снятие восстанавливают свойство кучи просеиванием — O(log n); корень (минимум по Comparable/Comparator) доступен за O(1) через peek. Для конкурентного варианта есть PriorityBlockingQueue.
Что хотят услышать
- Сложность основных операций и почему.
- Линейность remove и contains.
Частые ошибки
- Думать, что poll ищет минимум линейно.
- Считать peek дорогим.
Проверьте себя
Один верный вариант. Подумайте, потом откройте ответ.
Показать варианты и ответ
- ✗Все операции O(1): минимум хранится в корне
- ✗Все операции — O(log n), включая peek()
- ✓offer и poll — O(log n), peek — O(1)
- ✗offer — O(1), poll — O(n): минимум ищется линейным проходом
Что спросят дальше
- Как устроено просеивание (sift up/down)?
- Чем PriorityBlockingQueue отличается?
Разбор темы
- Очереди и стек: ArrayDeque и PriorityQueue
ArrayDeque как кольцевой буфер и замена Stack, PriorityQueue как бинарная куча и её неотсортированная итерация.
Связанные вопросы
Разбор собеседования с sotto
После собеседования sotto разбирает разговор: оценка, каждый вопрос — хорошо, частично или слабо, чего не хватило в ответе и над чем поработать к следующему разу. Первые 30 минут бесплатно.