Вы знакомы с контейнером, таким как куча?

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

Различают:

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

Распространенная реализация кучи — бинарная куча, которая обычно представляется в виде массива. Связь родитель-потомок определяется индексами массива:

• Левый потомок элемента с индексом i находится по индексу 2*i + 1.
• Правый потомок элемента с индексом i находится по индексу 2*i + 2.
• Родитель элемента с индексом i находится по индексу (i - 1) / 2.

Основные операции и их временная сложность (для бинарной кучи):

Применение кучи:

• Реал