Что делает heap push и как он добавляет элемент в кучу

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

Понимаете ли вы, что куча это не отсортированный массив, а частичный порядок, и почему вставка стоит логарифм. Для инженера данных вопрос обычно ведёт дальше, к задачам про топ K и приоритетные очереди.

Как отвечать

Куча это полное двоичное дерево, где родитель не больше своих детей (для min-heap). Хранится оно массивом: дети узла i лежат по индексам 2*i+1 и 2*i+2, родитель по (i-1)//2, никаких ссылок нет.

Вставка делается в два шага: элемент кладётся в конец массива, затем поднимается вверх, меняясь местами с родителем, пока свойство кучи нарушено. Это просеивание вверх, и высота дерева даёт O(log n) в худшем случае.

import heapq
h = []
heapq.heappush(h, (3, "c"))
heapq.heappush(h, (1, "a"))
heapq.heappop(h)

Дальше добавьте практическое, за этим вопрос и задают:

• heapq в Python умеет только min-heap, максимум делают отрицанием ключа;
• построение кучи из готового списка через heapify линейно, это дешевле, чем n вставок;
• для топ K держат кучу размером K и делают heappushpop, память O(K) вместо сортировки всего потока;
• вторым элементом кортежа кладут счётчик-тайбрейкер, иначе при равных приоритетах сравнение дойдёт до объекта, который сравнивать нельзя.

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

Считают кучу отсортированной. Упорядочен только корень, печать массива даёт частичный порядок, и утверждение «первые три элемента это три минимума» неверно.

Второе: меняют приоритет элемента прямо в массиве. Свойство кучи после этого нарушено, а heapq не умеет уменьшать ключ: в алгоритме Дейкстры вместо этого кладут новую пару и пропускают устаревшие при извлечении.

Третье: путают сложность вставки и построения. Называют O(n log n) для heapify или O(1) для вставки, хотя верно наоборот: построение линейно, вставка логарифмична.