Кучами будем называть такие структуры данных, которые позволяют выполнять две основные операции: "добавление элемента" и "удаление минимального элемента".
Если операция добавления элемента не требует дополнительных объяснений, то операция "удаления минимального элемента" предполагает, что для каждого элемента определено некоторое значение (ключ), по которому определяется "минимальность". В самом простом варианте значение ключа может совпадать со значением элемента. В общем случае соотношение значения элемента и его ключа могут иметь произвольную зависимость (пример).
Основным свойством (инвариантом) структуры данных куча является условие, что элементы в ней организованы таким образом, что приоритет любой вершины не ниже приоритета каждого из ее "сыновей". Так, если в качестве приоритета рассматривать время, которое элемент может "ожидать", то приоритет вершины будет тем выше, тем меньше время возможного ожидания.
Существует много способов реализации структуры данных "Куча", ниже будут рассмотрены некоторые из них:
Время выполнения различных операций для трёх видов сливаемых куч (n – общее число элементов в кучах на момент операции).
Процедура Двоичные кучи
(в худшем случае)Биномиальные кучи
(в худшем случае)Фибоначчиевы кучи
(учётная стоимость)Создание Q(1) Q(1) Q(1) Вставка Q(log n) O(log n) Q(1) Найти мин. Q(1) O(log n) Q(1) Удалить мин. Q(log n) Q(log n) O(log n) Слить Q(n) O(log n) Q(1) Уменьшить ключ Q(log n) Q(log n) Q(1) Удалить Q(log n) Q(log n) O(log n)