Изменения

'''Биномиальное дерево <tex>B_k</tex>''' (англ. ''binomial tree'') {{---}} [[Дерево, эквивалентные определения|дерево]], определяемое для каждого <tex>k = 0, 1, 2, \dots </tex> следующим образом: <tex>B_0</tex> {{---}} дерево, состоящее из одного узла; <tex>B_k</tex> состоит из двух биномиальных деревьев <tex>B_{k-1}</tex>, связанны связанных вместе таким образом, что корень одного из них является дочерним узлом корня второго дерева.

* Удаляем дерево <tex>B_k</tex> из кучи <tex>H</tex>. Иными словами , удаляем его корень из списка корней кучи. Это можно сделать за время <tex>O(1)</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>.

Биноминальную кучу можно сделать [[Персистентные структуры данных|персистентной]] при реализации на односвязных списках<ref>[https://github.com/kgeorgiy/okasaki/tree/master/Okasaki/Chapter3 Github {{---}} реализация на Haskell]</ref>. Для этого будем хранить список корней в порядке возрастания ранга, а детей будем хранить по убыванию ранга. Каждый родитель будет знать ребенка с большим рангом, который является головой списка детей, но ребенок не будет знать родителя. Односвязанные списки хороши с точки зрения функционального программирования, так как голова списка не будет достижима из потомков. Тогда при добавлениии новой версии в голову или удалении объявляя другую вершину новой головой мы не будем терять старые версии, которые останутся на месте, так как фактически односвязный список с операциями на голове это [[Персистентный стек|персистентный стек]], который является полностью персистентной функциональной структурой. При этом каждая версия будет поддерживать возможность изменения, что является полным уровнем персистентности. Это возможно благодаря тому, что нигде не делается уничтожающих присваиваний и не создается новых узлов в <tex>\mathrm{merge}</tex>. Также поддерживается операция <tex>\mathrm {merge}</tex> для всех версий биномиальных куч, что позволяет получать новую версию путём сливания старых. Это добавляет конфлюэнтный уровень персистентности. Персистентная биноминальная куча используется для [[Персистентная приоритетная очередь|персистентной приоритетной очереди]].