Минимальная куча¶

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

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

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

¶Структура хранения

На практике минимальная куча часто реализуется с помощью массива, где индексация начинается с 0 или 1. Для узла с индексом i:

• левый дочерний узел имеет индекс 2i + 1 (при индексации с 0) или 2i (при индексации с 1);
• правый дочерний узел — 2i + 2 (или 2i + 1);
• родительский узел — floor((i-1)/2) (или floor(i/2)).

Такое представление позволяет избежать использования указателей и ускоряет доступ к элементам.

¶Операции

¶Вставка элемента

Вставка нового элемента в минимальную кучу выполняется в два этапа:

1. Элемент добавляется в конец массива (на последнюю свободную позицию).
2. Выполняется процедура «всплытия» (sift-up, или heapify-up): элемент сравнивается с родительским узлом; если он меньше родителя, то они меняются местами. Процесс повторяется до тех пор, пока не будет восстановлено свойство кучи или элемент не достигнет корня.

Временная сложность — O(log n).

¶Извлечение минимального элемента

Удаление корневого узла (минимального элемента) включает следующие шаги:

1. Корень заменяется последним элементом массива.
2. Последний элемент удаляется.
3. Выполняется процедура «погружения» (sift-down, или heapify-down): новый корень сравнивается с дочерними узлами; если он больше любого из дочерних, то меняется местами с наименьшим из них. Процесс продолжается, пока свойство кучи не будет восстановлено.

Временная сложность — O(log n).

¶Поиск минимального элемента

Минимальный элемент всегда находится в корне, поэтому операция поиска выполняется за O(1).

¶Уменьшение ключа

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

1. Новое значение устанавливается меньше текущего.
2. Выполняется процедура всплытия для восстановления свойства кучи.

Временная сложность — O(log n).

¶Удаление произвольного элемента

Удаление произвольного элемента может быть выполнено путём уменьшения его ключа до минимального значения (например, до минус бесконечности) с последующим извлечением корня. Альтернативно, можно использовать операцию уменьшения ключа и затем извлечение минимального элемента.

¶Реализация на языках программирования

¶Пример на Python

```python class MinHeap: def __init__(self): self.heap = []

def parent(self, i): return (i - 1) // 2

def left_child(self, i): return 2 * i + 1

def right_child(self, i): return 2 * i + 2

def insert(self, key): self.heap.append(key) i = len(self.heap) - 1 while i > 0 and self.heap[self.parent(i)] > self.heap[i]: self.heap[self.parent(i)], self.heap[i] = self.heap[i], self.heap[self.parent(i)] i = self.parent(i)

def extract_min(self): if len(self.heap) == 0: return None if len(self.heap) == 1: return self.heap.pop() root = self.heap[0] self.heap[0] = self.heap.pop() self._sift_down(0) return root

def _sift_down(self, i): smallest = i left = self.left_child(i) right = self.right_child(i) if left < len(self.heap) and self.heap[left] < self.heap[smallest]: smallest = left if right < len(self.heap) and self.heap[right] < self.heap[smallest]: smallest = right if smallest != i: self.heap[i], self.heap[smallest] = self.heap[smallest], self.heap[i] self._sift_down(smallest)

def get_min(self): return self.heap[0] if self.heap else None ```

¶Пример на C++

В стандартной библиотеке C++ минимальная куча реализована через адаптер контейнера std::priority_queue с использованием компаратора std::greater:

```cpp

¶include <queue>

¶include <vector>

¶include <functional>

std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap; min_heap.push(10); min_heap.push(5); min_heap.push(20); int min_val = min_heap.top(); // 5 min_heap.pop(); ```

¶Применение

¶Пирамидальная сортировка

Минимальная куча используется в алгоритме пирамидальной сортировки (heapsort). Сначала из исходного массива строится куча, затем последовательно извлекаются минимальные элементы, формируя отсортированный массив. Временная сложность — O(n log n).

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

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

¶Приоритетные очереди

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

¶Сжатие данных (алгоритм Хаффмана)

В алгоритме Хаффмана для построения оптимального префиксного кода используется минимальная куча для выбора двух узлов с наименьшими частотами на каждом шаге.

¶Сравнение с максимальной кучей

Минимальная куча является зеркальным отражением максимальной кучи, где корень содержит максимальный элемент. Основные различия:

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

¶Ограничения и альтернативы

Минимальная куча не поддерживает эффективный поиск произвольного элемента (кроме корня) — для этого требуется O(n) времени. В таких случаях применяются более сложные структуры, такие как бинарные деревья поиска (например, AVL-деревья) или кучи Фибоначчи, которые позволяют выполнять уменьшение ключа за амортизированное O(1).

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

¶Интересные факты

• Термин «куча» (heap) в контексте структур данных был введён Дж. Уильямсом в 1964 году при описании пирамидальной сортировки.
• Минимальная куча может быть реализована не только на основе массива, но и с помощью указателей (динамическое дерево), однако массивный вариант более эффективен по памяти и кэш-производительности.
• В некоторых языках программирования, например в Java, минимальная куча реализована в классе PriorityQueue (по умолчанию — минимальная куча).