Куча-лес

Куча-лес (англ. heap forest) — в информатике и теории алгоритмов это структура данных, представляющая собой множество непересекающихся бинарных куч (англ. disjoint-set heap forest), в которой каждая куча организована по принципу «куча» (heap property) и поддерживает операции слияния (merge) и извлечения минимального элемента. Куча-лес является одной из реализаций сливаемой кучи (mergeable heap) и часто используется в алгоритмах, требующих динамического управления множествами с приоритетами, таких как алгоритм Прима для минимального остовного дерева или алгоритм Дейкстры для кратчайших путей.

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

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

Ключевые характеристики:

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

История

Понятие кучи как структуры данных было введено в 1964 году Дж. У. Дж. Уильямсом (J. W. J. Williams) в контексте пирамидальной сортировки (heapsort). Идея объединения нескольких куч в лес для поддержки операций слияния возникла позже, в 1970-х годах, в связи с развитием алгоритмов на графах. В 1978 году Майкл Фредман (Michael Fredman) и Роберт Тарьян (Robert Tarjan) предложили фибоначчиеву кучу (Fibonacci heap) — одну из наиболее эффективных реализаций сливаемой кучи, которая также может рассматриваться как разновидность кучи-леса. Однако термин «куча-лес» (heap forest) чаще используется для более простых реализаций, таких как левосторонние кучи (leftist heaps) или скошенные кучи (skew heaps), которые были разработаны в 1980-х годах.

Классификация

Кучи-леса можно классифицировать по способу организации деревьев и поддерживаемым операциям:

По типу кучи

• Минимальная куча-лес (min-heap forest): корень каждого дерева содержит минимальный элемент.
• Максимальная куча-лес (max-heap forest): корень каждого дерева содержит максимальный элемент.

По способу слияния

• Левосторонняя куча (leftist heap): каждое дерево поддерживает свойство «левосторонности» — расстояние до ближайшего пустого узла (нулевого указателя) слева не меньше, чем справа. Это обеспечивает логарифмическую сложность слияния.
• Скошенная куча (skew heap): деревья не имеют строгих ограничений на структуру, но при слиянии выполняется обмен левого и правого поддеревьев, что амортизированно даёт логарифмическую сложность.
• Биномиальная куча (binomial heap): лес состоит из биномиальных деревьев, каждое из которых имеет строго определённую структуру (количество узлов равно степени двойки). Слияние выполняется за логарифмическое время.
• Фибоначчиева куча (Fibonacci heap): лес из деревьев, не обязательно биномиальных, с отложенными операциями (ленивое слияние). Обеспечивает амортизированно константное время для вставки и слияния и логарифмическое — для извлечения минимума.

Устройство и операции

Куча-лес состоит из узлов, каждый из которых содержит:

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

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

• Создание кучи (make-heap): создание пустого леса.
• Вставка (insert): добавление нового узла в лес. Обычно создаётся новая куча из одного узла, которая затем сливается с существующим лесом.
• Слияние (merge): объединение двух куч в одну. В зависимости от реализации, слияние может выполняться путём объединения корней или перестроения деревьев.
• Извлечение минимума (extract-min): удаление корня с минимальным ключом и объединение его поддеревьев в новый лес.
• Поиск минимума (find-min): возврат корня с минимальным ключом без его удаления (обычно константное время, если минимум хранится отдельно).

Пример реализации: левосторонняя куча

В левосторонней куче каждое дерево имеет нулевой путь (null path length, NPL) — расстояние до ближайшего пустого узла. Свойство левосторонности: NPL левого потомка не меньше NPL правого. При слиянии двух куч сравниваются их корни: меньший корень становится новым корнем, а его правое поддерево сливается с другой кучей. После слияния, если NPL левого потомка меньше NPL правого, поддеревья меняются местами.

Сложность операций в левосторонней куче:

• Вставка: O(log n) в худшем случае.
• Слияние: O(log n) в худшем случае.
• Извлечение минимума: O(log n) в худшем случае.

Применение

Кучи-леса используются в задачах, где требуется динамическое управление множествами с приоритетами и частое слияние множеств:

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

Преимущества и недостатки

Преимущества

• Эффективное слияние: в отличие от обычной бинарной кучи, которая требует перестроения всего массива при слиянии, куча-лес позволяет объединять кучи за логарифмическое или даже амортизированно константное время.
• Динамическая структура: узлы могут добавляться и удаляться без необходимости перераспределения памяти, как в массиве.
• Гибкость: различные реализации (левосторонние, скошенные, биномиальные, фибоначчиевы кучи) позволяют выбирать оптимальный вариант под конкретные требования по времени и памяти.

Недостатки

• Накладные расходы на память: каждый узел содержит несколько указателей, что увеличивает потребление памяти по сравнению с бинарной кучей на массиве.
• Сложность реализации: некоторые варианты (например, фибоначчиева куча) требуют сложного управления структурами и отложенными операциями.
• Скорость доступа: поиск минимума может требовать дополнительного хранения указателя на минимальный корень, иначе он может быть O(n) в худшем случае.

Сравнение с другими структурами

Куча-лес занимает промежуточное положение между простыми бинарными кучами и сложными структурами, такими как фибоначчиевы кучи, обеспечивая баланс между производительностью и простотой реализации.

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

• Термин «куча-лес» (heap forest) не является общепринятым в русскоязычной литературе; чаще используется описательное название «лес куч» или «множество сливаемых куч». В англоязычных источниках термин heap forest встречается редко и обычно относится к конкретным реализациям, а не к общему классу структур.
• В некоторых контекстах куча-лес рассматривается как обобщение биномиальной кучи, где деревья не обязательно биномиальные.
• Алгоритмы слияния куч в лесу лежат в основе многих современных библиотек для работы с графами, например, в библиотеке Boost Graph Library (C++).

Источники

• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. — 3-е изд. — М.: Вильямс, 2013. — 1328 с.
• Седжвик Р. Фундаментальные алгоритмы на C++. Ч. 1–4. — М.: ДиаСофт, 2002. — 688 с.
• Fredman M. L., Tarjan R. E. Fibonacci heaps and their uses in improved network optimization algorithms // Journal of the ACM. — 1987. — Vol. 34, № 3. — P. 596–615.
• Okasaki C. Purely Functional Data Structures. — Cambridge University Press, 1998. — 220 с.