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

Куча (Heap) — это специализированная древовидная структура данных, которая удовлетворяет свойству кучи:

• Куча максимума: Для каждой вершины V, значение V больше или равно значению любого из ее дочерних узлов. Самый большой элемент находится в корне.
• Куча минимума: Для каждой вершины V, значение V меньше или равно значению любого из ее дочерних узлов. Самый маленький элемент находится в корне.

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

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

Основные операции:

• Вставка (Insertion): Элемент добавляется в конец массива, затем "всплывает" до правильной позиции, поддерживая свойство кучи. Сложность O(log n).
• Удаление (Deletion): Обычно удаляется корневой элемент (максимальный или минимальный). Корень заменяется последним элементом массива, который затем "опускается" до правильной позиции. Сложность O(log n).
• Извлечение максимума/минимума (Extract-Max/Extract-Min): Удаление корневого элемента. Сложность O(log n).
• Просмотр максимума/минимума (Peek-Max/Peek-Min): Просмотр корневого элемента без его удаления. Сложность O(1).

Применение:

• Очереди с приоритетом (Priority Queues).
• Алгоритмы сортировки (Heapsort).
• Реализация алгоритмов на графах (например, алгоритм Дейкстры).

Пример реализации кучи минимума с использованием массива:

python