Первая страница / Визуализаторы / Кучи /

Биномиальные деревья и биномиальные кучи

Голосование: 295, 252

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

Биномиальные деревья

Биномиальными деревьями (binomial trees) называются деревья с порядком на детях B0, B1, B2, …, определяемые индуктивно.

Рис. A Рис. B

Дерево В0 состоит из единственной вершины (рис. A). Дерево Bk склеено из двух экземпляров дерева Bk-1: корень одного из них объявлен самым левым ребёнком корня другого.

На рис. B показаны биномиальные деревья B0B4.

Лемма (свойства биномиальных деревьев). Дерево Bk:

  1. содержит 2k вершин;
  2. имеет высоту k;
  3. имеет Сki вершин глубины i;
  4. имеет корень, являющийся вершиной степени k; все остальные вершины имеют меньшую степень; дети корня являются корнями поддеревьев Bk-1, Bk-2, …, B1, B0 (слева направо).

Следствие. Максимальная степень вершины в биномиальном дереве с n вершинами равна logn.

Биномиальные кучи

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

  1. Каждое дерево в Н обладает свойством кучи (is heap-ordered), т. е. ключ каждой вершины не меньше, чем ключ её родителя.
  2. В H нет двух биномиальных деревьев одного размера (с одинаковой степенью корня).

Первое свойство гарантирует, что корень каждого из деревьев имеет наименьший ключ среди его вершин.

Из второго свойства следует, что суммарное количество вершин в биномиальной куче Н однозначно определяет размеры входящих в неё деревьев. В самом деле, общее число вершин, равное n, есть сумма размеров отдельных деревьев, которые суть различные степени двойки, а такое представление единственно (двоичная система счисления). Отсюда вытекает также, что куча с n элементами состоит из не более чем [logn]+1 биномиальных деревьев.

Представление биномиальных куч в программе

Каждое биномиальное дерево в биномиальной куче хранится в представлении левый ребёнок, правый сосед. Каждая вершина имеет поле key (ключ), а также хранит дополнительную информацию. Кроме того, каждая вершина х хранит указатели р[х] (родитель), child[x] (самый левый из детей) и sibling[x] (правый сосед, или «следующий по старшинству брат»). Если х — корень, то р[х]=NIL; если х не имеет детей, то child[x]=NIL, а если x является самым правым ребёнком своего родителя, то sibling[x]=NIL. Каждая вершина x содержит также поле degree[x], в котором хранится степень (число детей) вершины х.

Корни биномиальных деревьев, составляющих биномиальную кучу, связаны в список, называемый корневым списком (root list), в порядке возрастания степеней. Как мы видели, в куче с n вершинами степени корневых вершин образуют подмножество множества {0,1,…,[logn]}.

Для построения корневого списка используется поле sibling: для корневой вершины оно указывает на следующий элемент корневого списка (и содержит NIL для последнего корня в корневом списке).

Доступ к биномиальной куче Н осуществляется с помощью поля head[H] — указателя на первый корень в корневом списке кучи Н. Если куча Н пуста, то head[H]=NIL.

Запустить визуализатор

Операции с биномиальными кучами

Поиск минимального ключа

Эта процедура возвращает указатель на вершину с минимальным ключом в биномиальной куче, состоящей из n вершин.

В биномиальных деревьях наименьшие элементы стоят в корнях, так что достаточно выбрать минимальный элемент корневого списка. Длина корневого списка не превосходит [logn]+1, поэтому время работы процедуры есть O(logn).

Объединение двух куч

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

Вот в чем состоит ее суть: пусть есть две биномиальные кучи с t и n элементами. Размеры деревьев в них соответствуют слагаемым в разложениях чисел m и n в сумму степеней двойки. При сложении столбиком в двоичной системе происходят переносы, которые соответствуют слияниям двух биномиальных деревьев Bk-1 в дерево Вk. Надо только посмотреть, в каком из сливаемых деревьев корень меньше, и считать его верхним.

Работа этой процедуры начинается с соединения корневых списков куч в единый список, в котором корневые вершины идут в порядке возрастания их степеней.

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

Замечание. Добавление вершины в кучу осуществляется путем объединения данной кучи с кучей состоящей из одного элемента.

Удаление вершины с минимальным ключом

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

Все действия выполняются за время O(logn), так что общее время работы процедуры есть O(logn).

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

Следующая процедура уменьшает ключ элемента х биномиальной кучи, присваивая ему новое значение (-1). Вершина, ключ которой был уменьшен, «всплывает» наверх. Процедура выполняется за время O(logn), поскольку глубина вершины х есть O(logn) (утверждение леммы), а при выполнении каждого шага алгоритма мы поднимаемся вверх.

Удаление вершины

Удаление вершины сводится к двум предыдущим операциям: мы уменьшаем ключ до минимально возможного значения (в нашем случае (-1)), а затем удаляем вершину с минимальным ключом. В процессе выполнения процедуры это значение всплывает вверх, откуда и удаляется. Процедура выполняется за время O(logn).

Автор визуализатора: Билык Владислав

Описание интерфейса


Алексей / 2011-06-24 21:39:53

Биномиальное дерево имеет не 2k, а 2^k вершин.

Ваше имя
Email
Текущий день недели (строчными буквами)
Комментарий