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

Биномиальная куча — это структура данных, реализующая абстрактный тип данных «очередь с приоритетом» и представляющая собой набор биномиальных деревьев, удовлетворяющих свойству кучи (heap property). Биномиальная куча позволяет эффективно выполнять операции слияния (объединения) двух куч, что выгодно отличает её от бинарной кучи, где слияние требует линейного времени. Структура была предложена Жаном Вюйеменом в 1978 году.

Определение и основные свойства

Биномиальная куча состоит из нескольких биномиальных деревьев. Биномиальное дерево \( B_k \) рекурсивно определяется следующим образом:

• \( B_0 \) — дерево, состоящее из одного узла.
• \( B_k \) состоит из двух биномиальных деревьев \( B_{k-1} \), где корень одного из них является левым дочерним узлом корня другого.

Ключевые свойства биномиального дерева \( B_k \):

• Количество узлов в \( B_k \) равно \( 2^k \).
• Высота дерева равна \( k \).
• Корень имеет степень \( k \) (количество дочерних узлов), что больше, чем у любого другого узла в дереве.
• В дереве \( B_k \) на глубине \( i \) находится ровно \( \binom{k}{i} \) узлов (отсюда название «биномиальное»).

Биномиальная куча как структура данных удовлетворяет следующим условиям:

1. Каждое биномиальное дерево в куче подчиняется свойству кучи: ключ любого узла не меньше (для min-кучи) или не больше (для max-кучи) ключа его родительского узла.
2. Для любого неотрицательного целого \( k \) в куче существует не более одного биномиального дерева степени \( k \). Иными словами, набор деревьев соответствует двоичному представлению числа узлов в куче. Например, куча из 13 узлов (\( 13_{10} = 1101_2 \)) будет содержать деревья \( B_3 \), \( B_2 \) и \( B_0 \).

Представление в памяти

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

• ключ (значение, по которому определяется приоритет);
• указатель на родителя (parent);
• указатель на самого левого дочернего узла (child);
• указатель на следующего «брата» (sibling) — то есть на следующий узел в списке дочерних узлов одного родителя;
• степень (degree) — количество дочерних узлов.

Корни всех биномиальных деревьев, входящих в кучу, хранятся в виде односвязного списка, называемого списком корней (root list). Этот список упорядочен по возрастанию степеней деревьев.

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

Создание пустой кучи

Создаётся пустой список корней. Время выполнения: \( O(1) \).

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

Поскольку каждое биномиальное дерево в куче удовлетворяет свойству кучи, минимальный элемент находится среди корней деревьев. Для его поиска необходимо просмотреть список корней. Так как количество деревьев в куче не превышает \( O(\log n) \), время выполнения этой операции составляет \( O(\log n) \). При желании можно поддерживать указатель на минимальный корень, чтобы сократить время до \( O(1) \).

Слияние двух куч (Union)

Это ключевая операция, отличающая биномиальную кучу от бинарной. Слияние двух куч \( H_1 \) и \( H_2 \) выполняется следующим образом:

1. Списки корней \( H_1 \) и \( H_2 \) объединяются в один список, упорядоченный по возрастанию степеней.
2. Затем выполняется «проход» по списку: если обнаруживаются два дерева одинаковой степени, они сливаются в одно дерево степени на единицу больше. Слияние двух деревьев \( B_k \) заключается в том, что корень с большим ключом становится дочерним узлом корня с меньшим ключом.

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

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

Вставка нового элемента эквивалентна слиянию текущей кучи с кучей, содержащей единственный узел (дерево \( B_0 \)). Время выполнения: \( O(\log n) \). Амортизированное время, однако, составляет \( O(1) \), так как «дорогие» слияния происходят редко.

Извлечение минимального элемента (Extract-Min)

Операция выполняется в три этапа:

1. Найти корень с минимальным ключом в списке корней и удалить его.
2. Удалённый корень имел, предположительно, \( k \) дочерних узлов. Эти дочерние узлы (каждый из которых является корнем своего биномиального дерева степени от 0 до \( k-1 \)) образуют новую кучу. Список их корней необходимо перевернуть (так как в исходном представлении степени дочерних узлов убывают, а в списке корней должны возрастать).
3. Выполнить слияние исходной кучи (без удалённого корня) с новой кучей, полученной из дочерних узлов.

Время выполнения: \( O(\log n) \).

Уменьшение ключа (Decrease-Key)

Эта операция доступна только для min-кучи. После уменьшения ключа узла может быть нарушено свойство кучи. Для его восстановления узел «всплывает» вверх по дереву, обмениваясь ключами (или ссылками на узлы) с родителем, пока не будет восстановлен порядок. Время выполнения: \( O(\log n) \).

Удаление узла (Delete)

Удаление узла сводится к уменьшению его ключа до минимально возможного значения (например, до минус бесконечности) с последующим извлечением минимального элемента. Время выполнения: \( O(\log n) \).

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

Биномиальная куча занимает промежуточное положение между бинарной и фибоначчиевой кучами. Её главное преимущество — эффективное слияние, что делает её полезной в задачах, где требуется часто объединять очереди с приоритетом.

Применение

Биномиальные кучи находят применение в различных алгоритмах и системах:

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

Реализация на языке программирования (псевдокод)

Ниже приведён псевдокод основных операций для min-кучи.

``` Узел: key degree parent child sibling

Функция MergeTrees(B1, B2): Если B1.key > B2.key: Обменять B1 и B2 B2.parent = B1 B2.sibling = B1.child B1.child = B2 B1.degree = B1.degree + 1 Вернуть B1

Функция Union(H1, H2): H = новый список корней Пока H1 и H2 не пусты: Добавить в H корень с меньшей степенью Добавить оставшиеся корни Если H пуст: Вернуть H prev = null curr = H.head next = curr.sibling Пока next != null: Если curr.degree != next.degree ИЛИ (next.sibling != null И next.sibling.degree == curr.degree): prev = curr curr = next Иначе: curr = MergeTrees(curr, next) curr.sibling = next.sibling Если prev == null: H.head = curr Вернуть H

Функция Insert(H, key): node = новый узел с key H' = новая куча с node Вернуть Union(H, H')

Функция ExtractMin(H): Найти корень minNode с минимальным key в списке корней H Удалить minNode из списка корней H H' = новая куча из дочерних узлов minNode (в обратном порядке) H = Union(H, H') Вернуть H и minNode.key

Функция DecreaseKey(H, node, newKey): node.key = newKey Пока node.parent != null И node.key < node.parent.key: Обменять node.key и node.parent.key node = node.parent

Функция Delete(H, node): DecreaseKey(H, node, -∞) ExtractMin(H) ```

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

• Название «биномиальная» происходит от того, что количество узлов на \( i \)-м уровне дерева \( B_k \) равно биномиальному коэффициенту \( \binom{k}{i} \).
• Биномиальная куча является предшественницей фибоначчиевой кучи, которая была разработана для достижения амортизированного \( O(1) \) для операций вставки и уменьшения ключа.
• В отличие от бинарной кучи, которая представляет собой полное бинарное дерево, биномиальная куча является коллекцией деревьев, что делает её более гибкой для слияния.

Источники

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms (3rd edition). MIT Press, 2009.
• Jean Vuillemin. A Data Structure for Manipulating Priority Queues. Communications of the ACM, 1978.