333
правки
Изменения
Нет описания правки
=== makeHeap ===
Для создания пустой биномиальной пирамиды процедура makeBinomialHeap просто выделяет память и возвращает объект <tex>H</tex>, где <tex>head[H] = null</tex>, то есть пирамида не содержит элементов.
=== getMinimum ===
Асимптотика этой операции получается из того, что корней в этом списке не более <tex>\lfloor \log(n) \rfloor + 1</tex>.
При вызове этой процедуры для кучи, изображенной на картинке ниже, будет возвращен указатель на вершину с ключем <tex>1</tex>.
[[Файл:binHeapExample1.png|300px]]
Для этого нам надо сначала слить списки корней <tex>H_1, H_2</tex> в единый связный список, отсортированный по степеням в монотонно возрастающем порядке. Свойство пирамиды обеспечивает нам в новом списке наличие не более двух деревьев одинаковой степени. Далее мы за один проход по этому списку объединим некоторые деревья так, что в результате все они будут иметь попарно разные степени. На каждом шаге нам надо расмотреть несколько случаев.
* Рассматриваемое дерево и следующее за ним имеют разные степени (случай ''<tex>a'' </tex> на рисунке). Ситуация тривиальна и не требует никаких действий. Переходим к следующему шагу.* Текущее дерево и его два ближаших соседа справа (то есть те, которые встретятся на последующих итерациях) имеют одинаковые степени (случай ''<tex>b'' </tex> на рисунке). Эта ситуация хоть и не тривиальна, но ее следует оставить для следующего шага.* Если степень текущего и последующего деревьев одинакова (случай ''<tex>c-d'' </tex> на рисунке), то нам следует объединить их в новое дерево (сделав корнем вершину того дерева, чей ключ наименьший), степень которого будет на единицу больше той, что была ранее.
[[Файл:binHeapExample2.png|300]]
=== insert ===
Необходимо просто создать биномиальную пирамиду <tex>H'</tex> с одним узлом за время <tex>O(1)</tex> и объединяет ее с биномиальной пирамидой <tex>Н</tex>, содержащей <tex>n </tex> узлов, за время <tex>O(\log(n))</tex>.
=== extractMin ===
=== decreaseKey ===
Следующая процедура уменьшает ключ элемента <tex>x </tex> биномиальной кучи, присваивая ему новое значение. Вершина, ключ которой был уменьшен, «всплывает» наверх. Процедура выполняется за время <tex>O(\log n)</tex>, поскольку глубина вершины <tex>x </tex> есть <tex>O(\log n)</tex> (свойства биномиального дерева), а при выполнении каждого шага алгоритма мы поднимаемся вверх.
<code>
</code>
Пример работы процедуры проиллюстрирован на рисунке (<tex>y </tex> - уменьшаемый элемент, <tex>z </tex> - его предок).
[[Файл:binHeapExample3.png|400px]]
