Куча (структура данных)

В компьютерных науках куча — это специализированная структура данных типа дерево, которая удовлетворяет свойству кучи: если B является узлом-потомком узла A, то ключ(A) ≥ ключ(B). Из этого следует, что элемент с наибольшим ключом всегда является корневым узлом кучи, поэтому иногда такие кучи называют max-кучами.

Если сравнение перевернуть, то наименьший элемент будет всегда корневым узлом, такие кучи называют min-кучами.

Made with okso.app

Не существует никаких ограничений относительно того, сколько узлов-потомков имеет каждый узел кучи. На практике их число обычно не более двух. Куча является максимально эффективной реализацией абстрактного типа данных, который называется очередью с приоритетом.

Узел на вершине кучи, у которого нет родителей, называется корневым узлом.

Ссылки

• Wikipedia
• YouTube