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

Матеріал з Вікіпедії — вільної енциклопедії.

КУПА або піраміда (англ. heap) в інформатиці -- спеціалізована деревовидна структура даних, в якій існують певні властивості впорядкованості. Така структура даних повинна задовільняти основній властивості купи:

  • нехай А та B -- елементи купи, такі що B підпорядковане A (B - дитина А). Тоді значення B не повинно перевищувати А, тобто val[B] ≤ val[A]

Найбільш уживаним класом куп є бінарні купи.

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

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

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

[ред.] Дивись також