Выбор ответа Middle Стандартная библиотека обновлено
Макс-куча в heapq
Вопрос
Какой классический приём с heapq даёт максимальный элемент за O(log n) в любой версии Python?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: Класть в кучу -x, при извлечении менять знак. Исторически heapq реализует мин-кучу на списке (в Python 3.14 добавили публичные heapifymax, heappushmax, heappopmax, но код под старые версии и на собесах пишут так).
Варианты ответа
- Вызвать
heapq.heapify(lst, reverse=True)один раз - Использовать
heapq.heappop(lst, max=True)при извлечении - Отсортировать список по убыванию перед
heapify - Класть в кучу
-x, при извлечении менять знакправильный ответ
Разбор
Исторически heapq реализует мин-кучу на списке (в Python 3.14 добавили публичные heapify_max, heappush_max, heappop_max, но код под старые версии и на собесах пишут так). Классический приём: хранить отрицательные значения (или кортежи с отрицательным приоритетом). Параметров reverse и max у этих функций нет. Сортировка по убыванию перед heapify не помогает: после первой вставки снова работают правила мин-кучи.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.