Біноміальна купа — Вікіпедія
![](http://upload.wikimedia.org/wikipedia/commons/thumb/c/cf/Binomial_Trees.svg/500px-Binomial_Trees.svg.png)
Біноміальна купа (англ. binomial heap) — це множина біноміальних дерев, що задовольняє властивостям біноміальної купи:
- Кожне біноміальне дерево у купі підпорядковується властивості неспадної купи (англ. min-heap property): ключ вузла не менший за ключ його батьківського вузла.
- Для будь-якого невід'ємного цілого k в купі існує не більше одного біноміального дерева, чий корінь має ступінь k.
З даних властивостей випливає, що біноміальна купа, що має n вузлів, складається з не більше ніж біноміальних дерев.
Завдяки своїй структурі, біноміальне дерево ступеня k можна побудувати з двох дерев ступеня k−1 тривіальним приєднанням одного з них до іншого, як найлівішого підпорядкованого дерева. Ця властивість є центральною для операції злиття біноміальних дерев, яка становить їхню основну перевагу над звичайними купами.
Ім'я походить від того факту, що біноміальне дерево ступеня має вузлів на глибині .
Біноміальна купа втілена як множина біноміальних дерев які задовольняють властивостям біноміальної купи:
- Кожне біноміальне дерево у купі підкоряється властивості мінімальної купи: ключ вузла більше або дорівнює ключу його батьківського елемента.
- Наявні одне або нуль біноміальних дерев для кожного ступеня, включно з нульовим ступенем.
Перша властивість гарантує те, що корінь кожного дерева містить найменший ключ у дереві.
Друга властивість тягне за собою те, що біноміальна купа з n вузлами складається з не більше ніж log n + 1 біноміальних дерев. Насправді, кількість і ступені дерев однозначно визначаються кількістю вузлів n: кожне біноміальне дерево відповідає одному числу двійкового представлення числа n. Наприклад, число 13 є 1101 у двійковому форматі, , отже біноміальна купа з 13 вузлами складається з трьох біноміальних дерев ступенів 3, 2 і 0.
![Приклад біноміальної купи](http://upload.wikimedia.org/wikipedia/commons/thumb/6/61/Binomial-heap-13.svg/325px-Binomial-heap-13.svg.png)
Приклад біноміальної купи, що містить 13 вузлів з різними ключами.
Купи складається з біноміальних дерев ступенів 0, 2 і 3.
- Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. Розділ 6.1: Купи. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN 0-262-03384-4.