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

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

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

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

• Для элемента с индексом i (начиная с 0), его левый потомок находится по индексу 2i + 1.
• Его правый потомок находится по индексу 2i + 2.
• Его родитель находится по индексу floor((i - 1) / 2).

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

• Insert (Вставка): Добавление нового элемента. Время выполнения O(log n), где n — количество элементов.
• Extract-Max / Extract-Min (Извлечение): Удаление и возвращение максимального (в макс-куче) или минимального (в мин-куче) элемента. Время выполнения O(log n).
• Heapify (Построение кучи): Преобразование произвольного массива в кучу. Время выполнения O(n).

Кучи используются в алгоритмах сортировки (например, пирамидальная сортировка), в очередях с приоритетом, а также в алгоритмах поиска кратчайших путей (например, алгоритм Дейкстры).