Куча (Heap): Быстрый Min/Max

Цели урока

• Понять heap property (min/max)
• Узнать как хранить дерево в массиве
• Реализовать push, pop, peek
• Изучить heapify за O(n)

Предварительные знания

• Деревья

• Введение в деревья

В приёмном покое больницы не действует принцип 'первый пришёл - первый обслужен'. Пациент с сердечным приступом пройдёт раньше человека с порезом. Как реализовать такую очередь эффективно?

• ER triage - приоритет пациентов по тяжести
• Task schedulers - приоритетные очереди задач
• Dijkstra - поиск кратчайших путей
• Huffman coding - сжатие данных

Кучу придумали ради сортировки

В 1964 году Дж. У. Дж. Уильямс ввёл бинарную кучу как механизм нового метода сортировки - heapsort. В том же году Роберт Флойд опубликовал процедуру построения снизу вверх за O(n) - тот самый heapify, который превращает произвольный массив в кучу за линейное время вместо n отдельных вставок по O(log n). Спустя два десятилетия, в 1984 году, Майкл Фредман и Роберт Тарьян предложили фибоначчиевы кучи с амортизированным O(1) на decrease-key, улучшив теоретическую оценку алгоритмов Дейкстры и Прима, хотя из-за больших констант на практике обычно побеждает бинарная куча.

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

**Задача:** очередь с приоритетами. Пациенты в ER - кто тяжелее, того первым.

**Куча** - когда нужен частый доступ к min/max и частые вставки/удаления.

Heap Property: Родитель всегда лучше

**Min-Heap:** значение родителя ≤ значений детей. Корень - минимум.

**Max-Heap:** значение родителя ≥ значений детей. Корень - максимум.

Куча - это **complete binary tree** (заполняется слева направо, уровень за уровнем).

**Важно:** между siblings нет порядка! 3 и 2 в min-heap могут быть в любом порядке.

Хранение в массиве

Complete binary tree идеально хранится в массиве **без указателей**!

**Формулы навигации (0-indexed):**

Это делает кучу очень cache-friendly - все данные рядом в памяти!

Операции: Push и Pop

Push (вставка) - Sift Up

Pop (удаление min) - Sift Down

Heapify: Построение за O(n)

**Задача:** превратить произвольный массив в кучу.

**Наивно:** n вставок по O(log n) = O(n log n)

**Умно (heapify):** sift_down от середины к началу = **O(n)**!

Python: `heapq.heapify(arr)` - O(n) in-place heapify

Операции кучи

• peek (min/max): O(1)
• push: O(log n) - sift up
• pop: O(log n) - sift down
• heapify: O(n) - умное построение
• Хранение в массиве: parent(i)=(i-1)//2

Вопросы для размышления

• Сама структура complete binary tree позволяет хранить её в массиве без указателей. Что произойдёт с этой формулой parent/left/right, если разрешить дереву быть неполным - и почему 'жёсткое' заполнение по уровням здесь важнее произвольной формы?
• heapify работает за O(n), а n вставок - за O(n log n). Где ещё в алгоритмах встречается этот же контринтуитивный эффект 'построить сразу дешевле, чем добавлять по одному'?
• Куча даёт быстрый min или max, но не оба сразу. Какая структура решает обе задачи и какой компромисс приходится принять, чтобы получить такие двусторонние гарантии?

Следующие темы

Куча - мощный инструмент для множества алгоритмов.

• Применения кучи — Top-K, Median, Heap Sort

Связанные уроки

• ds-12-balanced-trees — Heap - частный случай полного дерева с heap property
• ds-15-heap-applications — Приложения heap: очереди приоритетов и алгоритм Дейкстры
• alg-07-heap-sort — Heap sort использует min-heap для сортировки за O(n log n)
• os-04-scheduling — Планировщики ОС используют priority queue на heap для задач
• alg-05-merge-sort