mirror of https://github.com/krahets/hello-algo.git synced 2026-03-21 04:17:31 +08:00

Files

krahets 8071daddaa First version.

2026-01-20 15:08:42 +08:00

16 KiB

Raw Permalink Blame History

Куча

Куча (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 (целочисленное деление вниз). Выход за пределы индексации обозначает пустой узел или его отсутствие.

Формулы индексации можно для удобства использования обернуть в функции.

[file]{my_heap}-[class]{max_heap}-[func]{parent}

Доступ к элементу на вершине кучи

Элемент на вершине кучи -- это корневой узел двоичного дерева, т. е. первый элемент списка.

[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)$. Ниже приведен код реализации.

[file]{my_heap}-[class]{max_heap}-[func]{sift_up}

Извлечение элемента с вершины кучи

Элемент на вершине кучи является корневым узлом двоичного дерева, т. е. первым элементом списка. Если просто удалить первый элемент из списка, индексы всех узлов в двоичном дереве изменятся, что затруднит дальнейшее исправление с помощью упорядочивания кучи. Чтобы минимизировать изменения индексов элементов, используется следующий порядок действий:

обмен вершины кучи с элементом в основании кучи (обмен корневого узла с самым правым листовым узлом);
после обмена удаляется элемент в основании кучи из списка (обратите внимание, что фактически удаляется исходный элемент на вершине кучи, так как они были поменяны);
упорядочивание кучи сверху вниз, начиная с корневого узла.

Направление операции упорядочивания кучи сверху вниз противоположно операции упорядочивания кучи снизу вверх, как показано на рисунке ниже. Значение корневого узла сравнивается со значениями его двух дочерних узлов, и самый большой дочерний узел обменивается с корневым узлом. Затем эта операция выполняется циклически, пока не будет достигнут листовой узел или не встретится узел, который не требует обмена.