Изменения

|statement=В биномиальном дереве <tex>B_k</tex> с <tex>n</tex> вершинами максимальная степень произвольного узла равна <tex>\log(n)</tex>.

Докажем это утверждение для корня. Степень остальных вершин меньше по предыдущему свойству. Так как степень корня дерева порядка <tex>k</tex> равна <tex>k</tex>, а узлов в этом дереве <tex>n = 2^k</tex>, то прологарифмировав обе части получаем, что <tex>k=O(\log(n))</tex>, то степень произвольного узла не более <tex>\log(n)</tex>.

|<math>\mathrm {insert}</math> |<tex>O(\log(n))</tex>

|<math>\mathrm {getMinimum}</math> |<tex>O(\log(n))</tex>

|<math>\mathrm {extractMin}</math> |<tex>\Theta(\log(n))</tex>

|<math>\mathrm {merge}</math> |<tex>\Omega(\log(n))</tex>

|<math>\mathrm {decreaseKey}</math> |<tex>\Theta(\log(n))</tex>

|<math>\mathrm {delete}</math> |<tex>\Theta(\log(n))</tex>

Так как корней в этом списке не более <tex>\lfloor \log(n) \rfloor + 1</tex>, то операция выполняется за <tex>O(\log(n))</tex>.

В получившемся списке могут встречаться пары соседних вершин одинаковой степени. Поэтому мы начинаем соединять деревья равной степени и делаем это до тех пор, пока деревьев одинаковой степени не останется. Этот процесс соответствует сложению двоичных чисел столбиком, и время его работы пропорционально числу корневых вершин, то есть операция выполняется за <tex>\Omega(\log(n))</tex>.

Чтобы добавить новый элемент в биномиальную кучу нужно создать биномиальную кучу <tex>H'</tex> с единственным узлом, содержащим этот элемент, за время <tex>O(1)</tex> и объединить ее с биномиальной кучей <tex>H</tex> за <tex>O(\log(n))</tex>, так как в данном случае куча <tex>H'</tex> содержит лишь одно дерево.

* Пусть <tex>H'</tex> {{---}} куча детей найденного корня. При этом мы для каждого из ребенка устанавливаем указатель на предка равным <tex>null</tex>. После этого сливаем кучу <tex>H'</tex> c <tex>H</tex> за <tex>\Omega(\log(n))</tex>.

Процедура выполняется за время <tex>\Theta(\log(n))</tex>, поскольку всего в списке <tex>\Theta(\log(n))</tex> корней биномиальных деревьев. И всего у найденного дерева <tex> k </tex> порядка (с минимальным значением ключа) ровно <tex> k </tex> детей, то сложность перебора этих детей будет тоже <tex>\Theta(\log(n))</tex>. А процесс слияния выполняется за <tex>\Omega(\log(n))</tex>. Таким образом операция выполняется <tex>\Theta(\log(n))</tex>.

Следующая процедура уменьшает ключ элемента <tex>x</tex> биномиальной кучи, присваивая ему новое значение. Вершина, ключ которой был уменьшен, «всплывает» как в обычной куче. Процедура выполняется за время <tex>\Theta(\log(n))</tex>, поскольку глубина вершины <tex>x</tex> в худшем случае есть <tex>\Theta(\log(n))</tex> (свойства биномиального дерева), а при выполнении каждого шага алгоритма мы поднимаемся вверх.

Удаление ключа сводится к операциям <math>\mathrm {decreaseKey }</math> и <math>\mathrm {extractMin}</math>: сначала нужно уменьшить ключ до минимально возможного значения, а затем извлечь вершину с минимальным ключом. В процессе выполнения процедуры этот узел всплывает вверх, откуда и удаляется. Процедура выполняется за время <tex>\Theta(\log(n))</tex>, поскольку каждая из операций, которые используется в реализации, работают за <tex>\Theta(\log(n))</tex>.

== Источники информации ==