Біноміальна купа

Біноміальні дерева ступенів від 0 до 3: Кожне дерево має кореневий вузол з піддеревами всіх нижчих ступенів. Наприклад, біноміальне дерево порядку 3 зв'язане з біноміальними деревами ступенів 2, 1 і 0 (підсвіченими відповідно синім, зеленим і червоним).

Біноміальна купа (англ. binomial heap) — це множина біноміальних дерев, що задовольняє властивостям біноміальної купи:

1. Кожне біноміальне дерево у купі підпорядковується властивості неспадної купи (англ. min-heap property): ключ вузла не менший за ключ його батьківського вузла.
2. Для будь-якого невід'ємного цілого k в купі існує не більше одного біноміального дерева, чий корінь має ступінь k.

З даних властивостей випливає, що біноміальна купа, що має n вузлів, складається з не більше ніж $\lfloor \;\log \;n\rfloor +1$ біноміальних дерев.

Завдяки своїй структурі, біноміальне дерево ступеня k можна побудувати з двох дерев ступеня k−1 тривіальним приєднанням одного з них до іншого, як найлівішого підпорядкованого дерева. Ця властивість є центральною для операції злиття біноміальних дерев, яка становить їхню основну перевагу над звичайними купами.

Ім'я походить від того факту, що біноміальне дерево ступеня $n$ має ${\tbinom {n}{d}}$ вузлів на глибині $d$.

Структура біноміальної купи

Біноміальна купа втілена як множина біноміальних дерев які задовольняють властивостям біноміальної купи:

• Кожне біноміальне дерево у купі підкоряється властивості мінімальної купи: ключ вузла більше або дорівнює ключу його батьківського елемента.

• Наявні одне або нуль біноміальних дерев для кожного ступеня, включно з нульовим ступенем.

Перша властивість гарантує те, що корінь кожного дерева містить найменший ключ у дереві.

Друга властивість тягне за собою те, що біноміальна купа з n вузлами складається з не більше ніж log n + 1 біноміальних дерев. Насправді, кількість і ступені дерев однозначно визначаються кількістю вузлів n: кожне біноміальне дерево відповідає одному числу двійкового представлення числа n. Наприклад, число 13 є 1101 у двійковому форматі, $2^{3}+2^{2}+2^{0}$, отже біноміальна купа з 13 вузлами складається з трьох біноміальних дерев ступенів 3, 2 і 0.

Приклад біноміальної купи, що містить 13 вузлів з різними ключами.
Купи складається з біноміальних дерев ступенів 0, 2 і 3.

Джерела

• Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. Розділ 6.1: Купи. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN 0-262-03384-4.