Что такое куча (в контексте структуры данных)?

Куча (heap) — это специализированное дерево, которое используется в качестве структуры данных. Основное свойство кучи - частичная упорядоченность: для любой вершины дерево соблюдается условие, что значение родительской вершины больше или равно значению любой из ее дочерних вершин (max-heap) или меньше или равно (min-heap).

Ключевые характеристики:

• Бинарное дерево: Чаще всего реализуется как бинарное дерево, где у каждого узла не более двух потомков.
• Полное бинарное дерево: На всех уровнях, кроме, возможно, последнего, дерево полностью заполнено. Узлы на последнем уровне заполняются слева направо. Это позволяет эффективно хранить кучу в виде массива.
• Свойство кучи:
  • Max-heap: Значение каждого узла больше или равно значениям его дочерних узлов. Максимальный элемент всегда находится в корне.
  • Min-heap: Значение каждого узла меньше или равно значениям его дочерних узлов. Минимальный элемент всегда находится в корне.

Основные операции с кучей:

• Вставка элемента: Добавление нового элемента и поддержание свойства кучи.
• Удаление элемента: Удаление корневого элемента (максимальн