Как работает сортировка в структуре heapq в Python

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

Знаете ли вы, что heapq это не отдельная структура, а набор функций над обычным списком, и какой инвариант они держат. Следом обычно просят решить задачу «k наибольших» или «слить k отсортированных списков» и спрашивают, почему не просто sorted().

Как отвечать

Куча в heapq это минимальная двоичная куча, уложенная в список: для каждого k выполняется heap[k] <= heap[2*k+1] и heap[k] <= heap[2*k+2]. Минимум всегда в heap[0], остальной список не отсортирован.

• heapify(lst): превращает список в кучу на месте за O(n), без копии;
• heappush и heappop: O(log n), элемент просеивается вверх или вниз;
• heapreplace и heappushpop: извлечение и вставка за одно просеивание, быстрее пары отдельных вызовов;
• nsmallest(k, it) и nlargest(k, it): около O(n log k), держат кучу размера k. При k, равном 1, уместнее min() и max(), при k, близком к n, быстрее sorted();
• *`merge(iterables)`**: ленивое слияние уже отсортированных последовательностей.

Сортировка через кучу это heapify плюс n вызовов heappop, итого O(n log n). На практике sorted() быстрее: Timsort использует уже упорядоченные куски данных и работает с лучшими константами. Куча выигрывает там, где полный порядок не нужен: топ-k, очередь с приоритетами, планировщик, алгоритм Дейкстры.

Максимальную кучу раньше делали через отрицание ключа, а в Python 3.14 появились heapify_max(), heappush_max() и heappop_max(). Для объектов без сравнения кладите кортеж (priority, counter, item): счётчик разрешает равные приоритеты и сохраняет порядок вставки.

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

Считают, что после heapify список отсортирован. Второй по величине элемент лежит в heap[1] или heap[2], а дальше порядок не гарантирован.

Кладут в кучу пары (priority, obj) и получают TypeError, когда приоритеты совпадают, а сами объекты между собой не сравниваются.

Работают с одной кучей из нескольких потоков. Функции heapq синхронизации не дают, для этого есть queue.PriorityQueue.