Купа (структура даних)

У комп'ютерних науках купа - це спеціалізована структура даних на кшталт дерева, яка задовольняє властивості купи: якщо B є вузлом-нащадком вузла A, то ключ (A) ≥ ключ (B). З цього випливає, що елемент із найбільшим ключем завжди є кореневим вузлом купи, тому іноді такі купи називають max-купами.

Якщо порівняння перевернути, то найменший елемент завжди буде кореневим вузлом, такі купи називають min-купами.

Made with okso.app

Не існує жодних обмежень щодо того, скільки вузлів-нащадків має кожен вузол купи. На практиці їх число зазвичай трохи більше двох. Купа є максимально ефективною реалізацією абстрактного типу даних, який називається чергою із пріоритетом.

Вузол на вершині купи, який не має батьків, називається кореневим вузлом.

Посилання

• Wikipedia