Куча (heap) — это специализированное дерево, которое используется в качестве структуры данных. Основное свойство кучи - частичная упорядоченность: для любой вершины дерево соблюдается условие, что значение родительской вершины больше или равно значению любой из ее дочерних вершин (max-heap) или меньше или равно (min-heap).
Ключевые характеристики:
- Бинарное дерево: Чаще всего реализуется как бинарное дерево, где у каждого узла не более двух потомков.
- Полное бинарное дерево: На всех уровнях, кроме, возможно, последнего, дерево полностью заполнено. Узлы на последнем уровне заполняются слева направо. Это позволяет эффективно хранить кучу в виде массива.
- Свойство кучи:
- Max-heap: Значение каждого узла больше или равно значениям его дочерних узлов. Максимальный элемент всегда находится в корне.
- Min-heap: Значение каждого узла меньше или равно значениям его дочерних узлов. Минимальный элемент всегда находится в корне.
Основные операции с кучей:
- Вставка элемента: Добавление нового элемента и поддержание свойства кучи.
- Удаление элемента: Удаление корневого элемента (максимального или минимального в зависимости от типа кучи) и поддержание свойства кучи.
- Создание кучи: Построение кучи из массива элементов.
Применение кучи:
- Сортировка: Алгоритм пирамидальной сортировки (Heapsort).
- Очереди с приоритетом: Эффективная реализация очередей, где элементы обрабатываются в порядке приоритета.
- Алгоритмы поиска: Например, поиск k-го по величине элемента.
- Алгоритмы на графах: Например, алгоритм Дейкстры.
Представление кучи массивом:
Поскольку куча является полным бинарным деревом, ее можно эффективно хранить в массиве без использования указателей.
- Если узел находится по индексу
i, его левый потомок находится по индексу 2*i + 1.
- Его правый потомок находится по индексу
2*i + 2.
- Его родитель находится по индексу
(i - 1) / 2.
python