Куча heap: быстрый минимум и очередь с приоритетами
💻 Информатика · 10 класс
Свойство двоичной кучи, индексы в массиве, подъём и спуск элемента на примере heapq.
Что называется кучей
Двоичная куча — структура данных для быстрого доступа к минимуму или максимуму. Здесь рассматриваем min-heap: значение родителя не больше значений его детей. Наименьший элемент находится в корне. В max-heap неравенство обратное, в корне расположен максимум.
Это значение слова heap не следует путать с областью динамической памяти программы. Куча как структура описывает организацию элементов, а не место, где операционная система выделила память.
Форма дерева и индексы
Уровни двоичного дерева заполняются сверху вниз, слева направо. Такую форму удобно хранить в массиве. При нумерации с нуля дети элемента i имеют индексы 2i+1 и 2i+2, если существуют, а родитель некорневого элемента — (i−1)//2.
Массив [2,5,3,9,7] задаёт корректную min-heap:2 не больше 5 и 3, а 5 не больше 9 и 7. Но весь массив не отсортирован:5 стоит перед 3. Свойство кучи сравнивает родителей с детьми, а не любые соседние позиции.
Как поддерживается свойство
При добавлении элемент сначала помещают в конец, сохраняя форму дерева. Если он меньше родителя, их меняют местами и продолжают подъём. Путь до корня содержит порядка log₂n уровней.
При извлечении минимума запоминают корень и переносят на его место последний элемент. Затем спускают его, выбирая меньшего из существующих детей. Отдельно учитывают один оставшийся ребёнок и пустую кучу. Перестановка с произвольным ребёнком может нарушить свойство.
Пример Python
import heapq
heap = [9, 2, 7, 5]
heapq.heapify(heap)
heapq.heappush(heap, 3)
print(heap[0])
print(heapq.heappop(heap))
print(heapq.heappop(heap))Вывод:2,2,3 на отдельных строках. Первое обращение только читает минимум. Первый heappop удаляет 2, поэтому следующим минимумом становится 3. Heapify преобразует список на месте; его результат не нужно присваивать обратно как новый список.
Сложность и назначение
Доступ к корню занимает O(1), добавление и извлечение — O(log n), построение через heapify — O(n). Полная сортировка последовательными извлечениями занимает O(n log n). Обычная куча не обеспечивает мгновенного поиска любого заданного значения.
Очередь с приоритетами выдаёт элемент по приоритету, а не обязательно по времени добавления. Например, можно хранить пары «числовой приоритет, задача». При равных приоритетах нужно заранее определить порядок и убедиться, что сравниваемые поля поддерживают сравнение.
Границы
Нельзя произвольно менять элемент внутри списка и считать, что свойство сохранилось. Нельзя вызывать heappop у пустой кучи без обработки ситуации: Python выбросит IndexError. Прикладной код должен определить, что означает отсутствие задач.
Практика
- Корректна ли min-heap [1,4,2,6]?
- Какие индексы детей у элемента 2 при нумерации с нуля?
- Удаляет ли heap[0] минимум?
Ответы
1. Да:1≤4,1≤2,4≤6. 2. 5 и 6, если они существуют. 3. Нет: это только чтение. Для удаления используют heappop, который также восстанавливает структуру. Не путайте свойство кучи с полной сортировкой списка.