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