Loading AI tools
З Вікіпедії, вільної енциклопедії
Купа[1], стіс[2][3] або піраміда (англ. heap) в інформатиці — спеціалізована деревоподібна структура даних, в якій існують певні властивості впорядкованості: якщо В — вузол нащадок A — тоді ключ(A) ≥ ключ(B). З цього випливає, що елемент з найбільшим ключем завжди є кореневим вузлом. Не існує ніяких обмежень щодо максимальної кількості елементів-нащадків, яку повинна мати кожна ланка, однак, на практиці, зазвичай, кожен елемент має не більше двох нащадків. Купа є однією із найефективніших реалізацій абстрактного типу даних, який має назву черга з пріоритетом. Купи відіграють критичну роль у низці ефективних алгоритмів роботи з графами, як то в алгоритмі Дейкстри та в алгоритмі сортування пірамідальне сортування. Найуживанішим класом куп є бінарні купи.
Базові операції з купою такі:
Купи часто використовуються для моделювання черг з пріоритетами.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.