Куча (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
Куча (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