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

потому что это основной компонент биномиальной кучи

Биномиальное дерево Bk – дерево, определяемое для каждого k = 0,1,2,… следующим образом: B0 – дерево, состоящее из одного узла; Bk состоит из двух биномиальных деревьев Bk-1, связанных вместе таким образом, что корень одного из них является дочерним узлом корня второго дерева

Биномиальная куча (англ. binomial heap) представляет собой множество биномиальных деревьев, которые удовлетворяют следующим свойствам:
каждое биномиальное дерево в куче подчиняется свойству неубывающей кучи: ключ узла не меньше ключа его родительского узла (упорядоченное в соответствии со свойством неубывающей кучи дерево),
для любого неотрицательного целого kk найдется не более одного биномиального дерева, чей корень имеет степень kk.

ссылка на детей осуществляется через левого ребенка, а остальные дети образуют односвязный список. Каждый узел в биномиальной куче представляется набором полей:
key — ключ (вес) элемента,
parent — указатель на родителя узла,
child — указатель на левого ребенка узла,
sibling — указатель на правого брата узла,
degree — степень узла (количество дочерних узлов данного узла).

Корни деревьев, из которых состоит куча, содержатся в так называемом списке корней, при проходе по которому степени соответствующих корней находятся в возрастающем порядке. Доступ к куче осуществляется ссылкой на первый корень в списке корней.

минимальным значением (предполагается, что ключей, равных ∞∞, нет).
Так как корней в этом списке не более ⌊logn⌋+1⌊log⁡n⌋+1, то операция выполняется за O(logn)O(log⁡n).
При вызове этой процедуры для кучи, изображенной на картинке ниже, будет возвращен указатель на вершину с ключом 11.

При использовании указателя на биномиальное дерево, которое содержит минимальный элемент, время для этой операции может быть сведено к O(1)O(1). Указатель должен обновляться при выполнении любой операции, кроме getMinimumgetMinimum. Это может быть сделано за O(logn)O(log⁡n), не ухудшая время работы других операций.

подпрограммы большинством остальных операций.
Вот в чем состоит ее суть: пусть есть две биномиальные кучи с HH и H′H′. Размеры деревьев в кучах соответствуют двоичным числам mm и nn, то есть при наличии дерева соответствующего порядка в этом разряде числа стоит единица, иначе ноль. При сложении столбиком в двоичной системе происходят переносы, которые соответствуют слияниям двух биномиальных деревьев Bk−1Bk−1 в дерево BkBk. Надо только посмотреть, в каком из сливаемых деревьев корень меньше, и считать его верхним (пример работы для одного случая приведен на рисунке справа; в другом случае подвешиваем наоборот).

Работа этой процедуры начинается с соединения корневых списков куч в единый список, в котором корневые вершины идут в порядке неубывания их степеней.
В получившемся списке могут встречаться пары соседних вершин одинаковой степени. Поэтому мы начинаем соединять деревья равной степени и делаем это до тех пор, пока деревьев одинаковой степени не останется. Этот процесс соответствует сложению двоичных чисел столбиком, и время его работы пропорционально числу корневых вершин, то есть операция выполняется за Ω(logn)Ω(log⁡n).

единственным узлом, содержащим этот элемент, за время O(1)O(1) и объединить ее с биномиальной кучей HH за O(logn)O(log⁡n), так как в данном случае куча H′H′ содержит лишь одно дерево.

и возвращает указатель на извлеченный узел.
Рассмотрим пошагово алгоритм:
Найдем биномиальное дерево с минимальным корневым значением. Предположим, что это дерево BkBk. Время работы этого шага алгоритма Θ(logn)Θ(log⁡n).
Удаляем дерево BkBk из кучи HH. Иными словами, удаляем его корень из списка корней кучи. Это можно сделать за время O(1)O(1).
Пусть H′H′ — куча детей найденного корня. При этом мы для каждого из ребенка устанавливаем указатель на предка равным nullnull. После этого сливаем кучу H′H′ c HH за Ω(logn)Ω(log⁡n).

Процедура выполняется за время Θ(logn)Θ(log⁡n), поскольку всего в списке Θ(logn)Θ(log⁡n) корней биномиальных деревьев. И всего у найденного дерева kk порядка (с минимальным значением ключа) ровно kk детей, то сложность перебора этих детей будет тоже Θ(logn)Θ(log⁡n). А процесс слияния выполняется за Ω(logn)Ω(log⁡n). Таким образом, операция выполняется Θ(logn)Θ(log⁡n).

ключ которой был уменьшен, «всплывает» как в обычной куче. Процедура выполняется за время Θ(logn)Θ(log⁡n), поскольку глубина вершины xx в худшем случае есть Θ(logn)Θ(log⁡n) (свойства биномиального дерева), а при выполнении каждого шага алгоритма мы поднимаемся вверх.

возможного значения, а затем извлечь вершину с минимальным ключом. В процессе выполнения процедуры этот узел всплывает вверх, откуда и удаляется. Процедура выполняется за время Θ(logn)Θ(log⁡n), поскольку каждая из операций, которые используется в реализации, работают за Θ(logn)Θ(log⁡n).

файлов, числа брались случайные от 1 до 10**10. Время работы в нс, в зависимости от кол-ва строк:
100 – 313 нс
1000 – 151 нс
10000 – 75 нс
100000 – 66 нс
500000 – 69 нс
1000000 – 67 нс

Были проведены замеры скорости работы алгоритма

412450 нс
100000 – 2264692 нс
500000 – 11815324 нс
1000000 – 19634195 нс