Выбор ответа Junior Куча спрашивают часто обновлено
Сложность операций кучи
Вопрос
Какая сложность у вставки, извлечения минимума и просмотра минимума в бинарной min-куче?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: O(log n), O(log n), O(1). Вставка просеивает элемент вверх по высоте дерева: O(log n).
Варианты ответа
- O(1), O(1), O(1)
- O(log n), O(log n), O(1)правильный ответ
- O(n), O(log n), O(1)
- O(log n), O(1), O(log n)
Разбор
Вставка просеивает элемент вверх по высоте дерева: O(log n). Извлечение переносит последний элемент в корень и просеивает вниз: O(log n). Минимум всегда в корне: O(1).
- Всё за O(1) невозможно, иначе сортировка была бы O(n).
- Вставка не O(n): сдвигать массив не нужно.
- Извлечение не O(1), а просмотр не O(log n).
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.