Двоичная куча

Двоичная куча (binary heap) — это структура данных, представляющая собой полное двоичное дерево, для которого выполняется свойство кучи: значение в каждом узле не меньше (или не больше) значений в его дочерних узлах. Двоичная куча является частным случаем кучи (приоритетной очереди) и широко применяется в алгоритмах сортировки (пирамидальная сортировка) и в алгоритмах поиска кратчайших путей (алгоритм Дейкстры).

Основные свойства

Двоичная куча реализуется на основе массива, где для элемента с индексом i (индексация обычно начинается с 0 или 1) его левый дочерний элемент находится по индексу 2i+1, правый — по индексу 2i+2, а родительский — по индексу floor((i-1)/2). Дерево является полным: все уровни, кроме последнего, заполнены полностью, а последний уровень заполняется слева направо без пропусков.

Различают два типа двоичных куч:

• Max-heap (максимальная куча): для любого узла i выполняется A[i] ≥ A[2i+1] и A[i] ≥ A[2i+2] (если дочерние узлы существуют). Корень содержит максимальный элемент.
• Min-heap (минимальная куча): для любого узла i выполняется A[i] ≤ A[2i+1] и A[i] ≤ A[2i+2]. Корень содержит минимальный элемент.

Высота двоичной кучи, содержащей n элементов, составляет O(log n). Это свойство обеспечивает логарифмическую сложность основных операций.

Основные операции

Вставка элемента (insert)

Новый элемент добавляется в конец массива (на последнюю свободную позицию), затем выполняется процедура «всплытия» (sift-up, heapify-up): элемент последовательно сравнивается с родительским и, если нарушается свойство кучи, меняется с ним местами. Процесс повторяется до восстановления порядка. Сложность: O(log n).

Извлечение корня (extract-max / extract-min)

Корневой элемент (максимальный в max-heap или минимальный в min-heap) удаляется. На его место помещается последний элемент массива, после чего выполняется процедура «погружения» (sift-down, heapify-down): элемент последовательно сравнивается с дочерними и, если нарушается свойство кучи, меняется местами с наибольшим (для max-heap) или наименьшим (для min-heap) дочерним. Сложность: O(log n).

Просмотр корня (peek)

Возвращает значение корневого элемента без его удаления. Сложность: O(1).

Построение кучи (heapify)

Из неупорядоченного массива можно построить двоичную кучу за O(n). Для этого применяется процедура heapify, начиная с последнего узла, имеющего хотя бы одного дочернего, и до корня. Для каждого узла выполняется sift-down. Этот метод эффективнее последовательной вставки n элементов, которая заняла бы O(n log n).

Применение

Пирамидальная сортировка (heapsort)

Алгоритм сортировки, основанный на двоичной куче. Сначала из массива строится max-heap, затем многократно извлекается корень (максимальный элемент) и помещается в конец массива. После каждого извлечения куча восстанавливается. Сложность: O(n log n) в худшем, среднем и лучшем случаях. Пирамидальная сортировка не требует дополнительной памяти (in-place).

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

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

Алгоритм Дейкстры

В алгоритме поиска кратчайших путей во взвешенном графе двоичная куча используется для выбора вершины с минимальным расстоянием. Это позволяет снизить временную сложность алгоритма с O(V^2) до O((V+E) log V), где V — число вершин, E — число рёбер.

Алгоритм Прима

При построении минимального остовного дерева графа двоичная куча применяется для выбора ребра с минимальным весом, инцидентного текущему дереву. Сложность: O(E log V).

Реализация на массиве

Двоичная куча обычно реализуется на динамическом массиве (например, std::vector в C++ или ArrayList в Java). Размер массива может изменяться при вставке и удалении элементов. Для эффективной работы с памятью часто используется резервирование места (capacity).

Пример реализации min-heap на псевдокоде:

``` class MinHeap: array: list size: int

function insert(value): array.append(value) size = size + 1 siftUp(size - 1)

function extractMin(): if size == 0: return error min = array[0] array[0] = array[size - 1] array.pop() size = size - 1 siftDown(0) return min

function siftUp(index): while index > 0: parent = (index - 1) // 2 if array[index] >= array[parent]: break swap(array[index], array[parent]) index = parent

function siftDown(index): while True: left = 2 index + 1 right = 2 index + 2 smallest = index if left < size and array[left] < array[smallest]: smallest = left if right < size and array[right] < array[smallest]: smallest = right if smallest == index: break swap(array[index], array[smallest]) index = smallest ```

Разновидности

Двоичная куча с поддержкой изменения ключа (decrease-key / increase-key)

В некоторых приложениях (например, в алгоритме Дейкстры) требуется изменить значение ключа уже находящегося в куче элемента. Для этого необходимо знать позицию элемента в массиве. После изменения ключа выполняется sift-up (если ключ уменьшился) или sift-down (если ключ увеличился). Для эффективного поиска позиции элемента часто используется дополнительная структура данных (например, хеш-таблица).

k-ичная куча (d-ary heap)

Обобщение двоичной кучи, где каждый узел имеет не два, а d дочерних элементов. При увеличении d уменьшается высота дерева (до O(log_d n)), но увеличивается время на sift-down (до O(d log_d n)). Применяется в некоторых алгоритмах, где важна скорость вставки.

Биномиальная куча и куча Фибоначчи

Более сложные структуры данных, поддерживающие операции слияния куч (merge) за логарифмическое или амортизированное константное время. Двоичная куча не поддерживает эффективное слияние — для объединения двух куч требуется перестроить одну из них за O(n).

Ограничения

• Двоичная куча не поддерживает эффективный поиск произвольного элемента (только корня). Для поиска требуется линейный проход по массиву.
• Слияние двух куч (merge) требует построения новой кучи из объединённого массива, что занимает O(n+m) времени.
• При частых операциях изменения ключа может потребоваться дополнительная память для хранения позиций элементов.

История

Термин «куча» (heap) в контексте структуры данных впервые был использован в 1964 году Дж. У. Дж. Уильямсом в статье, описывающей пирамидальную сортировку. Уильямс предложил алгоритм построения кучи за O(n log n) и саму сортировку. Позже, в 1964 году, Роберт Флойд улучшил процедуру построения кучи до O(n). С тех пор двоичная куча стала стандартной структурой данных, входящей в большинство учебников по алгоритмам и библиотек языков программирования.

Источники

• Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. «Алгоритмы: построение и анализ» (Introduction to Algorithms), 3-е издание.
• Дональд Кнут. «Искусство программирования», том 3: «Сортировка и поиск».
• Роберт Седжвик, Кевин Уэйн. «Алгоритмы на Java», 4-е издание.
• Williams, J. W. J. (1964). "Algorithm 232: Heapsort". Communications of the ACM.