|
|
| Строка 3: |
Строка 3: |
| | '''Биномиальное дерево <tex>B_k</tex>''' {{---}} [[Дерево, эквивалентные определения|дерево]], определяемое для каждого <tex>k = 0, 1, 2, \dots </tex> следующим образом: <tex>B_0</tex> - дерево, состоящее из одного узла высоты 0, то есть состоит из одного узла; <tex>B_k</tex> состоит из двух биномиальных деревьев <tex>B_{k-1}</tex>, связанны вместе таким образом, что корень одного из них является крайним левым дочерним узлом корня второго дерева.}} | | '''Биномиальное дерево <tex>B_k</tex>''' {{---}} [[Дерево, эквивалентные определения|дерево]], определяемое для каждого <tex>k = 0, 1, 2, \dots </tex> следующим образом: <tex>B_0</tex> - дерево, состоящее из одного узла высоты 0, то есть состоит из одного узла; <tex>B_k</tex> состоит из двух биномиальных деревьев <tex>B_{k-1}</tex>, связанны вместе таким образом, что корень одного из них является крайним левым дочерним узлом корня второго дерева.}} |
| | | | |
| − | Пример биномиального дерева для k = 0, 1, 2. | + | Пример биномиального дерева для k = 0, 2, 3. |
| | | | |
| | [[Файл:Example.jpg|325px|]] | | [[Файл:Example.jpg|325px|]] |
| Строка 9: |
Строка 9: |
| | '''Свойства биномиальных деревьев. ''' | | '''Свойства биномиальных деревьев. ''' |
| | Биномиальное дерево <tex>B_k</tex> с n вершинами: | | Биномиальное дерево <tex>B_k</tex> с n вершинами: |
| − | *имеет <tex>2^k</tex> узлов; | + | *име |
| − | *имеет высоту k;
| |
| − | *имеет ровно <tex>{k\choose i}</tex> узлов на высоте <tex>i = 0, 1, 2, \dots</tex>;
| |
| − | *имеет корень степени k; степерь всех остальных вершин меньше степени корня биномиального дерева;
| |
| − | *максимальная степень произвольного узла в биномиальном дереве с n узлами равна <tex>\log(n)</tex>.
| |
| − | | |
| − | {{Определение
| |
| − | |definition=
| |
| − | '''Биномиальная пирамида ([[Двоичная куча|куча]]) H''' {{---}} представляет собой множество биномиальных деревьев, которые удовлетворяют следующим свойствам '''биномиальных пирамид'''.
| |
| − | *Каждое биномиальное дерево в Н подчиняется свойству '''неубывающей пирамиды''': ключ узла не меньше ключа его родительского узла (упорядоченное в соответствии со свойсвом неубывающей прирамиды дерево).
| |
| − | *Для любого неотрицательного целого k найдется не более одного биномиального дерева Н, чей корень имеет степень K.}}
| |
| − | | |
| − | ==== Представление биномиальных куч ====
| |
| − | Поскольку количество детей у узлов варьируется в широких пределах, ссылка на детей осуществляется через левого ребенка, а остальные дети образуют односвязный список. Каждый узел в биномиальной пирамиде (куче) представляется набором полей:
| |
| − | *''key'' {{---}} ключ (вес) элемента;
| |
| − | *''parent'' {{---}} указатель на родителя узла;
| |
| − | *''child'' {{---}} указатель на левого ребенка узла;
| |
| − | *''sibling'' {{---}} указатель на правого брата узла;
| |
| − | *''degree'' {{---}} степень узла (количество дочерних узлов данного узла).
| |
| − | | |
| − | Корни деревьев, их которых состоит пирамида, содержатся в так называемом '''списке корней''', при проходе по которому степени соответствующих корней находятся в неубывающем порядке.
| |
| − | Доступ к куче осуществляется ссылкой на первый корень в списке корней.
| |
| − | | |
| − | == Операции над биномиальными пирамидами ==
| |
| − | | |
| − | ----
| |
| − | | |
| − | Рассмотрим операции, которые можно производить с биномиальной пирамидой. Их асимптотические оценки показаны в таблице.
| |
| − | {| border="1"
| |
| − | |Make_Heap
| |
| − | |<tex>\Theta(1)</tex>
| |
| − | |-
| |
| − | |Insert
| |
| − | |<tex>O(\log(n))</tex>
| |
| − | |-
| |
| − | |Minimum
| |
| − | |<tex>O(\log(n))</tex>
| |
| − | |-
| |
| − | |Extract_Min
| |
| − | |<tex>\Theta(\log(n))</tex>
| |
| − | |-
| |
| − | |Union
| |
| − | |<tex>\Omega(\log(n))</tex>
| |
| − | |-
| |
| − | |Decrease_Key
| |
| − | |<tex>\Theta(\log(n))</tex>
| |
| − | |-
| |
| − | |Delete
| |
| − | |<tex>\Theta(\log(n))</tex>
| |
| − | |}
| |
| − | | |
| − | === Make_Heap ===
| |
| − | Для создания пустой биномиальной приамиды процедура Make_Binomial_Heap просто выделяет память и возвращает объект H, где head[H] = nil, то есть пирамида не содержит элементов.
| |
| − | | |
| − | === Minimum ===
| |
| − | Для нахождения минимального элемента надо найти элемент в списке корней с минимальным значением (предполагается, что ключей, равных <tex>\infty</tex>, нет).
| |
| − | | |
| − | Асимптотика этой операции получается из того, что корней в этом списке не более <tex>\lfloor \log(n) \rfloor + 1</tex>.
| |
| − | | |
| − | При вызове этой процедуры для кучи, изображенной на картинке ниже, будет возвращен указатель на вершину с ключем 1.
| |
| − | | |
| − | [[Файл:Example2.jpg]]
| |
| − | | |
| − | === Union ===
| |
| − | Эта операция, соединяющая две биномиальные кучи в одну, используется в качестве подпрограммы большинством остальных операций.
| |
| − | | |
| − | Для этого нам надо сначала слить списки корней <tex>H_1, H_2</tex> в единый связный список, отсортированный по степеням в монотонно возрастающем порядке. Свойство пирамиды обеспечивает нам в новом списке наличие не более двух деревьев одинаковой степени. Далее мы за один проход по этому списку объединим некоторые деревья так, что в результате все они будут иметь попарно разные степени. На каждом шаге нам надо расмотреть несколько случаев.
| |
| − | | |
| − | * Рассматриваемое дерево и следующее за ним имеют разные степени (случай ''a'' на рисунке). Ситуация тривиальна и не требует никаких действий. Переходим к следующему шагу.
| |
| − | * Текущее дерево и его два ближаших соседа справа (то есть те, которые встретятся на последующих итерациях) имеют одинаковые степени (случай ''b'' на рисунке). Эта ситуация хоть и не тривиальна, но ее следует оставить для следующего шага.
| |
| − | * Если степень текущего и последующего деревьев одинакова (случай ''c-d'' на рисунке), то нам следует объединить их в новое дерево (сделав корнем вершину того дерева, чей ключ наименьший), степень которого будет на единицу больше той, что была ранее.
| |
| − | | |
| − | [[Файл:Example3.jpg]]
| |
| − | | |
| − | Пример пирамиды до Union и после:
| |
| − | | |
| − | [[Файл:Example5.jpg]]
| |
| − | | |
| − | === Inset ===
| |
| − | Необходимо просто создать биномиальную пирамиду <tex>H'</tex> с одним узлом за время <tex>O(1)</tex> и объединяет ее с биномиальной пирамидой Н, содержащей n узлов, за время <tex>O(\log(n))</tex>.
| |
| − | | |
| − | === Extract_Min ===
| |
| − | Приведенная ниже процедура извлекает узел с минимальным ключом из биномиальной кучи и возвращает указатель на извлеченный узел:
| |
| − | | |
| − | <code>
| |
| − | Binomial_Heap_Extract_Min(H)
| |
| − | поиск корня х с минимальным значением ключа в списке корней Н, и удаление х из корней Н
| |
| − | H' = Make_Binomial_Heap()
| |
| − | Обращение порядка связанного списка дочерних узлов х,
| |
| − | установка поля р каждого дочернего узла Н равным NIL
| |
| − | присвоение указателю head[H'] адреса заголовка
| |
| − | получающегося списка
| |
| − | H = Binomial_Heap_Union(H, H')
| |
| − | return x
| |
| − | </code>
| |
| − | | |
| − | Поскольку минимальный элемент находится в корневом списке, найти его легко; после его удаления соответствующее дерево рассыпается в набор биномиальных деревьев меньшего размера, который надо объединить с оставшейся частью кучи.
| |
| − | Все действия выполняются за время <tex>O\log(n)</tex>, так что общее время работы процедуры есть <tex>O\log(n)</tex>.
| |
| − | | |
| − | === Decrease_Key ===
| |
| − | Следующая процедура уменьшает ключ элемента х биномиальной кучи, присваивая ему новое значение. Вершина, ключ которой был уменьшен, «всплывает» наверх. Процедура выполняется за время <tex>O\log(n)</tex>, поскольку глубина вершины х есть <tex>O\log(n)</tex> (свойства биномиального дерева), а при выполнении каждого шага алгоритма мы поднимаемся вверх.
| |
| − | | |
| − | <code>
| |
| − | Binomial_Heap_Decrease_Key(H, x, k)
| |
| − | if k > key[x] then
| |
| − | return
| |
| − | key[x] = k
| |
| − | y = x
| |
| − | z = p[y]
| |
| − | while (z <tex>\ne</tex> NIL and key[y] < key[z]) do
| |
| − | swap(key[y], key[z])
| |
| − | y = z
| |
| − | z = p[y]
| |
| − | </code>
| |
| − | | |
| − | Пример работы процедуры проиллюстрирован на рисунке (y - уменьшаемый элемент, z - его предок).
| |
| − | | |
| − | [[Файл:Example6.jpg|600px]]
| |
| − | | |
| − | === Delete ===
| |
| − | Удаление ключа сводится к двум предыдущим операциям: мы уменьшаем ключ до минимально возможного значения, а затем удаляем вершину с минимальным ключом. В процессе выполнения процедуры это значение всплывает вверх, откуда и удаляется. Процедура выполняется за время <tex>O\log(n)</tex>.
| |
| − | | |
| − | <code>
| |
| − | Binomial_Heap_Delete(H, x)
| |
| − | Binomial_Heap_Decrease_Key(H, x, -<tex>\infty</tex>)
| |
| − | Binomial_Heap_Extract_Min(H)
| |
| − | </code>
| |
| − | | |
| − | == Источники ==
| |
| − | ----
| |
| − | * [http://www.intuit.ru/department/algorithms/dscm/7/ INTUIT.ru |Биномиальные кучи]
| |
| − | * [http://en.wikipedia.org/wiki/Binomial_heap Wikipedia | Binomial_heap]
| |
| − | * Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 538-558.
| |
