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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

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