Какая сложность у операции heap push

Что проверяют

Знаете ли вы, как устроена двоичная куча, и умеете ли применить её там, где она нужна в работе с данными: top-k, слияние отсортированных потоков, очередь с приоритетом. Следом почти всегда спрашивают, сколько стоит построить кучу из готового массива.

Как отвечать

push стоит O(log n) в худшем случае. Элемент кладётся в конец массива за O(1), затем «всплывает», меняясь с родителем, пока нарушен порядок кучи. Куча это полное двоичное дерево высотой ⌊log₂ n⌋, поэтому подъёмов не больше высоты.

Что делает ответ сильным:

• средний случай: на случайных данных новый элемент в среднем поднимается на константное число уровней, и средняя стоимость O(1). Худший случай для min-кучи наступает, когда приходит новый минимум;
• heapq в Python: heappush и heappop за O(log n), а heapify строит кучу из списка за O(n), а не за O(n log n), как n отдельных вставок. heappushpop и heapreplace дешевле пары отдельных вызовов;
• только min-куча: для max-кучи кладут отрицательные значения или кортежи (-score, item). При равных приоритетах Python начнёт сравнивать сами элементы, поэтому добавляют счётчик: (priority, counter, item);
• top-k по потоку: держите min-кучу размера k и заменяйте минимум, когда приходит элемент больше. Итог O(n log k) по времени и O(k) по памяти, это работает даже на данных, которые не помещаются в память. Для готового списка есть heapq.nlargest(k, data).

Где ещё встречается: heapq.merge для слияния отсортированных файлов, алгоритм Дейкстры, планировщики задач.

Где спотыкаются

Отвечают O(1) без оговорок, путая запись в конец массива со всей операцией.

Строят кучу циклом из heappush там, где хватило бы heapify, и не могут объяснить, почему построение линейное.

Забывают, что в heapq нет изменения приоритета и удаления произвольного элемента за O(log n). Обычно старую запись помечают удалённой и пропускают при извлечении.