# Куча
Куча (heap) -- это полное двоичное дерево, удовлетворяющее определенным условиям, и делится на два основных типа, как показано на рисунке ниже.
- Минимальная куча (min heap): значение любого узла ≤ значений его дочерних узлов.
- Максимальная куча (max heap): значение любого узла ≥ значений его дочерних узлов.
Куча, как частный случай полного двоичного дерева, обладает следующими свойствами:
- узлы на самом нижнем уровне заполняются слева, остальные уровни полностью заполнены;
- корневой узел двоичного дерева называется вершиной кучи, а самый правый узел на нижнем уровне -- основанием кучи;
- для максимальной (минимальной) кучи значение элемента на вершине (т. е. корневом узле) является наибольшим (наименьшим).
## Основные операции с кучей
Следует отметить, что многие языки программирования содержат приоритетную очередь (priority queue), которая является абстрактной структурой данных, определяемой как очередь с приоритетной сортировкой.
На практике **куча часто используется для реализации приоритетной очереди, где максимальная куча соответствует приоритетной очереди, из которой элементы извлекаются в порядке убывания**. С точки зрения использования приоритетную очередь и кучу можно считать эквивалентными структурами данных. Поэтому в данной книге они не различаются и называются просто кучей.
Основные операции с кучей представлены в таблице ниже, названия методов в разных языках программирования могут отличаться.
Таблица Эффективность операций с кучей
| Метод | Описание | Временная сложность |
| ----------- | ---------------------------------------------------------- | ------------------- |
| `push()` | Вставка элемента в кучу | $O(\log n)$ |
| `pop()` | Извлечение элемента с вершины кучи | $O(\log n)$ |
| `peek()` | Доступ к элементу на вершине кучи (макс./мин. значение) | $O(1)$ |
| `size()` | Получение количества элементов в куче | $O(1)$ |
| `isEmpty()` | Проверка кучи на пустоту | $O(1)$ |
В реальных приложениях можно напрямую использовать классы кучи (или приоритетной очереди), предоставляемые языком программирования.
Подобно сортировочным алгоритмам по возрастанию и по убыванию, можно установить флаг или изменить компаратор для преобразования минимальной кучи в максимальную и наоборот. Ниже приведен пример кода.
=== "Python"
```python title="heap.py"
# Инициализация минимальной кучи
min_heap, flag = [], 1
# Инициализация максимальной кучи
max_heap, flag = [], -1
# Модуль heapq в Python по умолчанию реализует минимальную кучу
# Рассматривается вариант, при котором элементы инвертируются перед
# добавлением в кучу, что позволяет изменить порядок и реализовать максимальную кучу
# В этом примере flag = 1 соответствует минимальной куче, flag = -1 -- максимальной
# Вставка элемента в кучу
heapq.heappush(max_heap, flag * 1)
heapq.heappush(max_heap, flag * 3)
heapq.heappush(max_heap, flag * 2)
heapq.heappush(max_heap, flag * 5)
heapq.heappush(max_heap, flag * 4)
# Доступ к элементу на вершине кучи
peek: int = flag * max_heap[0] # 5
# Извлечение элемента с вершины кучи
# Извлеченные элементы образуют последовательность по убыванию
val = flag * heapq.heappop(max_heap) # 5
val = flag * heapq.heappop(max_heap) # 4
val = flag * heapq.heappop(max_heap) # 3
val = flag * heapq.heappop(max_heap) # 2
val = flag * heapq.heappop(max_heap) # 1
# Получение размера кучи
size: int = len(max_heap)
# Проверка кучи на пустоту
is_empty: bool = not max_heap
# Построение кучи из списка
min_heap: list[int] = [1, 3, 2, 5, 4]
heapq.heapify(min_heap)
```
## Реализация кучи
Ниже приведена реализация максимальной кучи. Для преобразования в минимальную кучу достаточно инвертировать все логические сравнения (например, заменить ≥ на ≤). Заинтересованные читатели могут реализовать это самостоятельно.
### Хранение и представление кучи
В разделе «Двоичные деревья» упоминалось, что полные двоичные деревья удобно представлять в виде массива. **Поскольку куча является таким деревом, для ее хранения будем использовать массив**.
При использовании массива для представления двоичного дерева элементы представляют значения узлов, а индексы -- их положение в дереве. **Указатели на узлы реализуются через формулы индексации**.
Как показано на рисунке ниже, для заданного индекса массива $i$ индекс левого дочернего узла равен $2i + 1$, правого -- $2i + 2$, а индекс родительского узла -- $(i - 1) / 2$ (целочисленное деление вниз). Выход за пределы индексации обозначает пустой узел или его отсутствие.
Формулы индексации можно для удобства использования обернуть в функции.
```src
[file]{my_heap}-[class]{max_heap}-[func]{parent}
```
### Доступ к элементу на вершине кучи
Элемент на вершине кучи -- это корневой узел двоичного дерева, т. е. первый элемент списка.
```src
[file]{my_heap}-[class]{max_heap}-[func]{peek}
```
### Вставка элемента в кучу
Нам дан элемент `val`, который сначала добавляется в основание кучи. После добавления условия корректности кучи могут быть нарушены, поскольку элемент `val` может быть больше других элементов кучи. **Поэтому необходимо восстановить порядок на пути от вставленного узла до корневого узла**. Эта операция называется упорядочиванием кучи (heapify).
Рассмотрим **выполнение упорядочивания кучи снизу вверх**, начиная с узла, который был добавлен. Как показано на рисунке ниже, необходимо сравнивать значения вставленного узла и его родительского узла. Если вставленный узел больше, они меняются местами. Затем продолжается выполнение этой операции с исправлением каждого узла кучи снизу вверх, пока не будет достигнут корневой узел или не встретится узел, который не требует обмена.
=== "<1>"
=== "<2>"
=== "<3>"
=== "<4>"
=== "<5>"
=== "<6>"
=== "<7>"
=== "<8>"
=== "<9>"
Пусть общее количество узлов равно $n$, тогда высота дерева будет $O(\log n)$. Из этого следует, что максимальное количество циклов операции упорядочивания кучи также будет $O(\log n)$. **Тогда и временная сложность операции добавления элемента в кучу составит $O(\log n)$**. Ниже приведен код реализации.
```src
[file]{my_heap}-[class]{max_heap}-[func]{sift_up}
```
### Извлечение элемента с вершины кучи
Элемент на вершине кучи является корневым узлом двоичного дерева, т. е. первым элементом списка. Если просто удалить первый элемент из списка, индексы всех узлов в двоичном дереве изменятся, что затруднит дальнейшее исправление с помощью упорядочивания кучи. Чтобы минимизировать изменения индексов элементов, используется следующий порядок действий:
1. обмен вершины кучи с элементом в основании кучи (обмен корневого узла с самым правым листовым узлом);
2. после обмена удаляется элемент в основании кучи из списка (обратите внимание, что фактически удаляется исходный элемент на вершине кучи, так как они были поменяны);
3. **упорядочивание кучи сверху вниз**, начиная с корневого узла.
**Направление операции упорядочивания кучи сверху вниз противоположно операции упорядочивания кучи снизу вверх**, как показано на рисунке ниже. Значение корневого узла сравнивается со значениями его двух дочерних узлов, и самый большой дочерний узел обменивается с корневым узлом. Затем эта операция выполняется циклически, пока не будет достигнут листовой узел или не встретится узел, который не требует обмена.
=== "<1>"
=== "<2>"
=== "<3>"
=== "<4>"
=== "<5>"
=== "<6>"
=== "<7>"
=== "<8>"
=== "<9>"
=== "<10>"
Подобно операции добавления элемента в кучу, временная сложность операции извлечения элемента с вершины кучи также составляет $O(\log n)$. Ниже приведен код реализации.
```src
[file]{my_heap}-[class]{max_heap}-[func]{sift_down}
```
## Типичные применения кучи
- **Приоритетная очередь**: куча обычно является предпочтительной структурой данных для реализации приоритетной очереди, операции вставки и извлечения имеют временную сложность $O(\log n)$, а операция построения кучи -- $O(n)$, все эти операции очень эффективны.
- **Пирамидальная сортировка**: для заданного набора данных можно построить кучу, а затем последовательно извлекать элементы, получая отсортированные данные. Однако обычно используется более элегантный способ реализации пирамидальной сортировки, подробности см. в разделе «Пирамидальная сортировка».
- **Получение наибольших $k$ элементов**: это классическая алгоритмическая задача и типичное применение, например, выбор 10 самых популярных новостей для горячих тем в Weibo, выбор 10 самых продаваемых товаров и т. д.