Что такое куча?

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

• Макс-куча (Max-heap): Значение ключа каждой вершины не меньше значения ключа её детей. Максимальный элемент находится в корне.
• Мин-куча (Min-heap): Значение ключа каждой вершины не больше значения ключа её детей. Минимальный элемент находится в корне.

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

• Для элемента с индексом i (начиная с