Биномиальная куча
Определение: |
Биномиальное дерево дерево, определяемое для каждого следующим образом: - дерево, состоящее из одного узла высоты 0, то есть состоит из одного узла; состоит из двух биномиальных деревьев , связанны вместе таким образом, что корень одного из них является крайним левым дочерним узлом корня второго дерева. | —
Пример биномиального дерева для k = 0, 1, 2.
Свойства биномиальных деревьев. Биномиальное дерево
с n вершинами:- имеет узлов;
- имеет высоту k;
- имеет ровно узлов на высоте ;
- имеет корень степени k; степерь всех остальных вершин меньше степени корня биномиального дерева;
- максимальная степень произвольного узла в биномиальном дереве с n узлами равна .
Определение: |
Биномиальная пирамида (куча) H — представляет собой множество биномиальных деревьев, которые удовлетворяют следующим свойствам биномиальных пирамид.
|
Содержание
Представление биномиальных куч
Поскольку количество детей у узлов варьируется в широких пределах, ссылка на детей осуществляется через левого ребенка, а остальные дети образуют односвязный список. Каждый узел в биномиальной пирамиде (куче) представляется набором полей:
- key — ключ (вес) элемента;
- parent — указатель на родителя узла;
- child — указатель на левого ребенка узла;
- sibling — указатель на правого брата узла;
- degree — степень узла (количество дочерних узлов данного узла).
Корни деревьев, их которых состоит пирамида, содержатся в так называемом списке корней, при проходе по которому степени соответствующих корней находятся в неубывающем порядке. Доступ к куче осуществляется ссылкой на первый корень в списке корней.
Операции над биномиальными пирамидами
Рассмотрим операции, которые можно производить с биномиальной пирамидой. Их асимптотические оценки показаны в таблице.
Make_Heap | |
Insert | |
Minimum | |
Extract_Min | |
Union | |
Decrease_Key | |
Delete |
Make_Heap
Для создания пустой биномиальной приамиды процедура Make_Binomial_Heap просто выделяет память и возвращает объект H, где head[H] = nil, то есть пирамида не содержит элементов.
Minimum
Для нахождения минимального элемента надо найти элемент в списке корней с минимальным значением (предполагается, что ключей, равных
, нет).Асимптотика этой операции получается из того, что корней в этом списке не более
.При вызове этой процедуры для кучи, изображенной на картинке ниже, будет возвращен указатель на вершину с ключем 1.
Union
Эта операция, соединяющая две биномиальные кучи в одну, используется в качестве подпрограммы большинством остальных операций.
Процедура Binomial_Heap_Union многократно связывает биномиальные деревья с корнями одинаковой степени. Приведенная далее процедура связывает дерево
Binomial_Link(y, z) p[y] = z sibling[y] = child[z] child[z] = y degree[z]++
Приведенная далее процедура сливает биномиальные кучи
, возвращая получаемую в результате биномиальную прирамиду. удаляются. Процедура Binomial_Heap_Merge сливает списки корней в единый связный список, отсортированный по степеням в монотонно возрастающем порядке.
Binomial_Heap_Union() H = Make_Binomial_Heap() head[H] = Binomial_Heap_Merge( ) delete //удаление объектов, но не списков, на которые они указывают if head[H] = NIL then return H prex_x = NIL x = head[H] next_x = sibling[x] while next_x NIL do if (degree[x] degree[next_x]) or (sibling[next_x] NIL and degree[sibling[next_x]] = degree[x]) then prex_x = x else if key[x] <= key[next_x] then sibling[x] = sibling[next_x] Binomial_Link(next_x, x) else if prev_x = NIL then head[H] = next_x else sibling[prev_x] = next_x Binomial_Link(x, next_x) x = next_x next_x = sibling[x]
Inset
Приведенная ниже процедура вставляет узел х в биномиальную пирамиду Н (предполагается, что для х уже выделена память и поле key[x] уже заполнено):
Binomial_Heap_Insert(H, x) H' = Make_Binpmial_Heap p[x] = NIL child[x] = NIL sibling[x] = NIL degree[x] = 0 head[H'] = x H = Binomial_Heap_Union(H, H')
Процедура просто создает биномиальную пирамиду H' с одним узлом за время О(1) и объединяет ее с биномиальной пирамидой Н, содержащей n узлов, за время О(lg(n)).
Extract_Min
Приведенная ниже процедура извлекает узел с минимальным ключок из биномиальной кучи и возвращает указатель на извлеченный узел:
Binomial_Heap_Extract_Min(H) поиск корня х с минимальным значением ключа в списке корней Н, и удаление х из корней Н H' = Make_Binomial_Heap() Обращение порядка связанного списка дочерних узлов х, установка поля р каждого дочернего узла Н равным NIL присвоение указателю head[H'] адреса заголовка получающегося списка H = Binomial_Heap_Union(H, H') return x
Поскольку минимальный элемент находится в корневом списке, найти его легко; после его удаления соответствующее дерево рассыпается в набор биномиальных деревьев меньшего размера, который надо объединить с оставшейся частью кучи. Все действия выполняются за время O(lgn), так что общее время работы процедуры есть O(lgn)
Decrease_Key
Следующая процедура уменьшает ключ элемента х биномиальной кучи, присваивая ему новое значение. Вершина, ключ которой был уменьшен, «всплывает» наверх. Процедура выполняется за время O(lgn), поскольку глубина вершины х есть O(lgn) (свойства биномиального дерева), а при выполнении каждого шага алгоритма мы поднимаемся вверх.
Binomial_Heap_Decrease_Key(H, x, k)
if k > key[x] then
return
key[x] = k
y = x
z = p[y]
while (z
NIL and key[y] < key[z]) do
swap(key[y], key[z])
y = z
z = p[y]
Delete
Удаление ключа сводится к двум предыдущим операциям: мы уменьшаем ключ до минимально возможного значения, а затем удаляем вершину с минимальным ключом. В процессе выполнения процедуры это значение всплывает вверх, откуда и удаляется. Процедура выполняется за время O(lgn).
Binomial_Heap_Delete(H, x)
Binomial_Heap_Decrease_Key(H, x, -
)
Binomial_Heap_Extract_Min(H)
Источники
- INTUIT.ru |Биномиальные кучи
- Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 538-558.