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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Біноміальні дерева ступенів від 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.