Куча и приоритетная очередь

Зачем нужна куча

Куча (heap) — структура, которая всегда быстро отдаёт минимальный (или максимальный) элемент. Вставка и извлечение минимума — O(log n), а посмотреть минимум — O(1). Это идеально для приоритетной очереди: обрабатывать задачи по важности, а не по порядку поступления.

Куча — это бинарное дерево, где каждый родитель не больше своих детей (min-heap). Поэтому в корне всегда минимум. В Python куча хранится в обычном спискеИзменяемая упорядоченная коллекция элементов: [1, 2, 3]. По-английски list., а работать с ней помогает модуль heapq.

heapify делает из списка кучу на месте. heappush добавляет элемент, heappop извлекает и возвращает минимум, сохраняя свойство кучи. Так можно «вытаскивать» элементы по возрастанию по одному.

Приоритетная очередь

Если хранить в куче кортежиНеизменяемая упорядоченная коллекция: (1, 2). Похож на список, но менять нельзя. По-английски tuple. (приоритет, данные), она автоматически отдаёт элемент с наименьшим приоритетом первым. Это и есть приоритетная очередь — основа планировщиков задач и алгоритмаЧёткая последовательность шагов для решения задачи за конечное число действий. Дейкстры.

Задача top-K

Классика собеседований: найти K наибольших элементов. Сортировать весь массив — O(n log n). С кучей размера K это O(n log k): держим в куче только K элементов, и когда приходит больший — выталкиваем минимальный. Для частого случая есть готовые heapq.nlargest и heapq.nsmallest.

Напечатается 5. Поскольку у меньшего отрицательного числа больший модуль, наверху кучи окажется -5, а смена знака при извлечении даёт 5. Так min-heap превращают в max-heap — частый приём на собеседовании.

⚠️ Частые ошибки новичков

Ошибка. Думать, что вся куча отсортирована. Свойство кучи гарантирует минимум только в корне (heap[0]); остальной список не отсортирован. Чтобы получить элементы по порядку, их нужно извлекать через heappop. Запустите код и убедитесь, что печать списка кучи не даёт отсортированный порядок.