Меню Главная Случайная статья Настройки Биномиальная куча Материал из https://ru.wikipedia.org Биномиальная куча (англ. binomial heap) — структура данных, реализующая абстрактный тип данных «очередь с приоритетом». Конструируется как набор биномиальных деревьев — объектов, задаваемых рекуррентно следующим образом:[1] биномиальное дерево нулевого ранга состоит из одной вершины; биномиальное дерево ранга ${\displaystyle k}$ представляет собой вершину и ${\displaystyle k}$ детей, ранг которых последовательно уменьшается с ${\displaystyle k-1}$ до 0. Таким образом, биномиальное дерево ранга ${\displaystyle k}$ содержит ${\displaystyle 2^{k}}$ вершин и имеет ${\displaystyle C_{k}^{d}}$ вершин на глубине ${\displaystyle d}$, в честь чего оно и получило своё название. Из двух деревьев ранга ${\displaystyle k-1}$ можно образовать одно ранга ${\displaystyle k}$ путём подвешивания одного из них к корню другого в качестве ${\displaystyle k}$-ой ветви. Биномиальная куча обладает двумя свойствами: ключ каждой вершины не меньше ключа её родителя; все биномиальные деревья имеют разный размер. Из этих свойств вытекают два следствия. Во-первых, корень каждого из деревьев имеет наименьший ключ среди его вершин. Во-вторых, суммарное количество вершин в биномиальной куче однозначно определяет размеры входящих в неё деревьев. Например, биномиальная куча с ${\displaystyle 13=2^{3}+2^{2}+2^{0}}$ вершинами состоит из трёх деревьев высотой 3, 2 и 0 и имеющих, соответственно, 8, 4 и 1 элементов. Следующие операции выполняются за время ${\displaystyle O(\log n)}$, где ${\displaystyle n}$ — число вершин: вставка нового элемента (амортизационная сложность — ${\displaystyle O(1)}$), нахождение элемента с минимальным ключом, удаление элемента с минимальным ключом, уменьшение значения ключа данного элемента, удаление данного элемента, объединение двух куч. Таким образом, биномиальная куча является сливаемой кучей, то есть кроме стандартных операций очереди с приоритетом (добавления, удаления, извлечения минимума, изменения ключей) предоставляет дополнительную операцию слияния двух куч. Примечания Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Глава 19. Биномиальные пирамиды // Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — С. 537—558. — ISBN 5-8459-0857-4.