Куча, очередь с приоритетом

Структура данных «куча» (heap) – это дерево с одним простым свойством: значение каждого узла «больше» значения всех его дочерних узлов. Это дерево не обязано быть бинарным, сбалансированным, или иметь какие-либо еще свойства.

Таким образом, сложность получения самого большого элемента – всегда константная. Сложность добавления и поиска других элементов зависит от остальных свойств.

Такое построение делает кучу наилучшей реализацией структуры «очередь с приоритетом». В очереди с приоритетом в отличие от LIFO и FIFO очередей, выбывает не самый старый или новый элемент, а самый большой. В хипе это всегда корень дерева, и когда он убывает, новым корнем становится самый большой из его подузлов.

Описанная куча иногда еще называется max heap. Если делать родителем, наоборот, самый маленький элемент – полученная структура будет называться min heap.

Эта структура данных не имеет ничего общего с понятием heap в оперативной памяти.