Loading AI tools
З Вікіпедії, вільної енциклопедії
Біноміальна купа (англ. binomial heap) — це множина біноміальних дерев, що задовольняє властивостям біноміальної купи:
З даних властивостей випливає, що біноміальна купа, що має n вузлів, складається з не більше ніж біноміальних дерев.
Завдяки своїй структурі, біноміальне дерево ступеня k можна побудувати з двох дерев ступеня k−1 тривіальним приєднанням одного з них до іншого, як найлівішого підпорядкованого дерева. Ця властивість є центральною для операції злиття біноміальних дерев, яка становить їхню основну перевагу над звичайними купами.
Ім'я походить від того факту, що біноміальне дерево ступеня має вузлів на глибині .
Біноміальна купа втілена як множина біноміальних дерев які задовольняють властивостям біноміальної купи:
Перша властивість гарантує те, що корінь кожного дерева містить найменший ключ у дереві.
Друга властивість тягне за собою те, що біноміальна купа з n вузлами складається з не більше ніж log n + 1 біноміальних дерев. Насправді, кількість і ступені дерев однозначно визначаються кількістю вузлів n: кожне біноміальне дерево відповідає одному числу двійкового представлення числа n. Наприклад, число 13 є 1101 у двійковому форматі, , отже біноміальна купа з 13 вузлами складається з трьох біноміальних дерев ступенів 3, 2 і 0.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.