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