Купа стіс або піраміда англ heap в інформатиці спеціалізована деревоподібна структура даних в якій існують певні властив

Купа, стіс або піраміда (англ. heap) в інформатиці — спеціалізована деревоподібна структура даних, в якій існують певні властивості впорядкованості: якщо В — вузол нащадок A — тоді ключ(A) ≥ ключ(B). З цього випливає, що елемент з найбільшим ключем завжди є кореневим вузлом. Не існує ніяких обмежень щодо максимальної кількості елементів-нащадків, яку повинна мати кожна ланка, однак, на практиці, зазвичай, кожен елемент має не більше двох нащадків. Купа є однією із найефективніших реалізацій абстрактного типу даних, який має назву черга з пріоритетом. Купи відіграють критичну роль у низці ефективних алгоритмів роботи з графами, як то в алгоритмі Дейкстри та в алгоритмі сортування пірамідальне сортування. Найуживанішим класом куп є бінарні купи.

Базові операції з купою такі:

підтримка основної властивості купи
побудова купи з невпорядкованого масиву
сортування купи
видалення найменшого елемента
отримання найбільшого елемента
додавання елемента

Купи часто використовуються для моделювання черг з пріоритетами.

Див. також

Примітки

Кормен, Томас; Лейзерсон, Чарльз; Рівест, Рональд; Стайн, Кліфорд (2019), Розділ 6.1: Купи, Вступ до алгоритмів (вид. 3), К.І.С., с. 168—171, ISBN
heap // Англійсько-український словник з математики та інформатики / уклад. Є. Мейнарович, М. Кратко. — 2010.
Кочерга О., Мейнарович Є. Англійсько-українсько-англійський словник наукової мови (фізика та споріднені науки). [ 7 березня 2016 у Wayback Machine.] — Вінниця: Нова книга, 2010.

Джерела

Томас Кормен; Чарльз Лейзерсон, Рональд Рівест, Кліфорд Стайн (2009) [1990]. Розділ 6: Сортування купою. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN .

[mit-1] Кормен, Томас; Лейзерсон, Чарльз; Рівест, Рональд; Стайн, Кліфорд (2019), Розділ 6.1: Купи, Вступ до алгоритмів (вид. 3), К.І.С., с. 168—171, ISBN

[2] // Англійсько-український словник з математики та інформатики / уклад. Є. Мейнарович, М. Кратко. — 2010.

[3] Кочерга О., Мейнарович Є. Англійсько-українсько-англійський словник наукової мови (фізика та споріднені науки). [ 7 березня 2016 у Wayback Machine.] — Вінниця: Нова книга, 2010.