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

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

Приклад повної бінарної купи

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

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

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

Див. також

Примітки

  1. Кормен, Томас; Лейзерсон, Чарльз; Рівест, Рональд; Стайн, Кліфорд (2019). Розділ 6.1: Купи. Вступ до алгоритмів (вид. 3). К.І.С. с. 168–171. ISBN 978-617-684-239-2.
  2. heap // Англійсько-український словник з математики та інформатики / уклад. Є. Мейнарович, М. Кратко. — 2010.
  3. Кочерга О., Мейнарович Є. Англійсько-українсько-англійський словник наукової мови (фізика та споріднені науки). — Вінниця: Нова книга, 2010.

Джерела

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.