Рубрики

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

Основное применение Binary Heap — это реализация очереди приоритетов. Binomial Heap — это расширение Binary Heap, которое обеспечивает более быструю операцию объединения или слияния вместе с другими операциями, предоставляемыми Binary Heap.

Биноминальная куча — это коллекция биномиальных деревьев

Что такое биномиальное дерево?
Биномиальное дерево порядка 0 имеет 1 узел. Биномиальное дерево порядка k можно построить, взяв два биномиальных дерева порядка k-1 и сделав одно из них левым дочерним или другим.
Биномиальное дерево порядка k имеет следующие свойства.
а) Он имеет ровно 2 k узлов.
б) имеет глубину k.
c) На глубине i ровно k C i узлов для i = 0, 1,. , , , к.
г) Корень имеет степень k, а потомки корня сами являются биномиальными деревьями с порядком k-1, k-2, .. 0 слева направо.

Следующая диаграмма ссылается на 2-е издание книги CLRS .

Биноминальная куча:
Биномиальная куча — это набор биномиальных деревьев, где каждое биномиальное дерево следует за свойством Min Heap. И может быть не более одного биномиального дерева любой степени.

Примеры Биноминальной Кучи:

12------------10--------------------20
             /  \                 /  | \
           15    50             70  50  40
           |                  / |    |     
           30               80  85  65 
                            |
                           100
A Binomial Heap with 13 nodes. It is a collection of 3 
Binomial Trees of orders 0, 2 and 3 from left to right. 

    10--------------------20
   /  \                 /  | \
 15    50             70  50  40
 |                  / |    |     
 30               80  85  65 
                  |
                 100

Биноминальная куча с 12 узлами. Это коллекция из 2
Биноминальные деревья порядков 2 и 3 слева направо.

Двоичное представление числа и биномиальных куч
Биномиальная куча с n узлами имеет количество биномиальных деревьев, равное количеству установленных битов в двоичном представлении n. Например, пусть n равно 13, в двоичном представлении n (00001101) 3 заданных бита, следовательно, 3 биномиальных дерева. Мы также можем связать степень этих биномиальных деревьев с позициями установленных битов. С этим соотношением мы можем заключить, что в биномиальной куче имеется O (Logn) биномиальных деревьев с n узлами.

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

1) insert (H, k): вставляет ключ «k» в биномиальную кучу «H». Эта операция сначала создает биномиальную кучу с одним ключом 'k', затем вызывает объединение на H и новую биномиальную кучу.

2) getMin (H): простой способ getMin () состоит в том, чтобы просмотреть список корней биномиальных деревьев и вернуть минимальный ключ. Эта реализация требует времени O (Logn). Его можно оптимизировать до O (1), поддерживая указатель на минимальный корень ключа.

3) extractMin (H): эта операция также использует union (). Сначала мы вызываем getMin (), чтобы найти минимальный ключ биномиального дерева, затем удаляем узел и создаем новую биномиальную кучу, соединяя все поддеревья удаленного минимального узла. Наконец, мы вызываем union () для H и недавно созданную биномиальную кучу. Эта операция требует времени O (Logn).

4) delete (H): как и Binary Heap, операция удаления сначала уменьшает ключ до минус бесконечности, а затем вызывает extractMin ().

5) уменьшение ключа (H): уменьшение ключа () также похоже на двоичную кучу. Мы сравниваем ключ уменьшения с его родителем, и если ключ родителя больше, мы меняем ключи и возвращаемся к родителю. Мы останавливаемся, когда достигаем узла, у которого родительский ключ имеет меньший ключ, или мы достигаем корневого узла. Временная сложность lowerKey () равна O (Logn).

Объединение операций в Биноминальной Кучи:
Для двух биномиальных куч H1 и H2 объединение (H1, H2) создает одну биномиальную кучу.
1) Первый шаг — просто объединить две кучи в неубывающем порядке градусов. На следующей диаграмме рисунок (b) показывает результат после слияния.

2) После простого слияния нам нужно убедиться, что существует не более одного биномиального дерева любого порядка. Для этого нам нужно объединить биномиальные деревья одного порядка. Мы просматриваем список объединенных корней, отслеживаем три указателя, prev, x и next-x. Могут быть следующие 4 случая, когда мы пересекаем список корней.
—– Случай 1: порядки x и next-x не совпадают, мы просто продвигаемся вперед.
В следующих 3 случаях порядки x и next-x одинаковы.
—– Случай 2: Если порядок next-next-x также такой же, двигайтесь вперед.
—– Случай 3: если ключ x меньше или равен ключу next-x, то сделайте next-x дочерним по отношению к x, связав его с x.
—– Случай 4: Если ключ от x больше, то сделать x потомком следующего.

Следующая диаграмма взята из 2-го издания книги CLRS .

Как изобразить биноминальную кучу?
Биноминальная куча — это набор биномиальных деревьев. Биномиальное дерево должно быть представлено таким образом, чтобы обеспечить последовательный доступ ко всем братьям и сестрам, начиная с самого левого брата (это нужно нам, а также в extractMin () и delete ()). Идея состоит в том, чтобы представить биномиальные деревья как крайнее левое дочернее и правое одноуровневое представление, т. Е. Каждый узел хранит два указателя, один на самый левый дочерний элемент, а другой на правый одноуровневый элемент.

Реализация биномиальной кучи

Источники:
Введение в алгоритмы от Клиффорда Стейна, Томаса Х. Кормена, Чарльза Э. Лизерсона, Рональда Л.

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

Рекомендуемые посты:

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

0.00 (0%) 0 votes