Какая суммарная сложность решения задачи с кучей

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

Умеете ли вы сложить стоимость отдельных операций в оценку всего решения и заметить, от какого размера кучи она зависит. Типичная задача: найти k самых больших элементов из n, и следом звучит вопрос, чем это лучше сортировки.

Как отвечать

Сначала операции двоичной кучи:

• вставка и извлечение корня: O(log m), где m это текущий размер кучи. В Python это heapq.heappush и heapq.heappop;
• чтение корня: O(1), это heap[0];
• построение: heapq.heapify за O(n) просеиванием снизу вверх. Вставка n элементов по одному даёт O(n log n);
• поиск или удаление произвольного элемента: O(n), куча упорядочена только вдоль пути от корня к листьям.

Суммарная сложность это число операций, умноженное на логарифм размера кучи. Отсюда главные ответы:

• top-k из n: min-куча размером k, каждый новый элемент сравниваем с корнем и при необходимости делаем heapreplace. Итого O(n log k) по времени и O(k) по памяти. Сортировка дала бы O(n log n) и требовала бы держать в памяти всё, а куча работает на потоке. Готовое решение: heapq.nlargest;
• слияние k отсортированных источников: O(N log k), где N это общее число элементов. Типичный случай в data engineering: внешняя сортировка файлов, которые не влезают в память, через heapq.merge;
• медиана потока: две кучи, max и min, O(log n) на вставку и O(1) на ответ.

heapq реализует min-кучу. Классический приём для max-кучи: класть отрицательные значения или кортеж (-priority, item).

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

Для top-k складывают в кучу все n элементов и получают O(n log n), теряя весь выигрыш. Размер кучи должен быть k.

Путают тип кучи: для k наибольших нужна min-куча, потому что в корне должен лежать самый маленький из отобранных, он вытесняется первым.

Кладут в кучу кортежи (priority, obj) с одинаковыми приоритетами. Python начинает сравнивать сами объекты и падает с TypeError, если это, например, словари. Спасает счётчик вторым элементом: (priority, counter, obj).