Ответ
Куча (heap) — это специализированная древовидная структура данных, которая удовлетворяет свойству кучи: если A является родительским узлом для B, то значение в узле A упорядочено относительно значения в узле B. Обычно куча реализуется на основе бинарного дерева.
Типы куч:
- Min-heap (минимальная куча): Значение каждого родительского узла меньше или равно значениям его дочерних узлов. Таким образом, минимальный элемент всегда находится в корне дерева.
- Max-heap (максимальная куча): Значение каждого родительского узла больше или равно значениям его дочерних узлов. Максимальный элемент — в корне.
Ключевые операции и их сложность:
insert(добавление): O(log n) — добавление нового элемента с сохранением свойства кучи.extract-min/extract-max(извлечение): O(log n) — удаление корневого (минимального/максимального) элемента.heapify(построение): O(n) — преобразование неупорядоченного массива в кучу.
Пример на Python (модуль heapq):
Модуль heapq в Python реализует min-heap.
import heapq
# Неупорядоченный список
data = [3, 1, 4, 1, 5, 9, 2, 6]
# Преобразуем список в min-heap (на месте)
heapq.heapify(data)
# Теперь data: [1, 1, 2, 3, 5, 9, 4, 6] (не отсортирован, но является кучей)
# Добавляем новый элемент
heapq.heappush(data, 0)
# data: [0, 1, 1, 3, 5, 9, 4, 6, 2]
# Извлекаем наименьший элемент
smallest = heapq.heappop(data) # smallest = 0
print(f"Извлечен элемент: {smallest}")
# data после извлечения: [1, 1, 2, 3, 5, 9, 4, 6]Где применяется:
- Приоритетные очереди (Priority Queues): Наиболее частое применение.
- Алгоритм Дейкстры: Для эффективного выбора узла с наименьшим расстоянием.
- Пирамидальная сортировка (Heapsort).
- Поиск k-го наибольшего/наименьшего элемента в коллекции.