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

Куча (heap) — это специализированное дерево, которое используется в качестве структуры данных. Основное свойство кучи - частичная упорядоченность: для любой вершины дерево соблюдается условие, что значение родительской вершины больше или равно значению любой из ее дочерних вершин (max-heap) или меньше или равно (min-heap).

Ключевые характеристики:

• Бинарное дерево: Чаще всего реализуется как бинарное дерево, где у каждого узла не более двух потомков.
• Полное бинарное дерево: На всех уровнях, кроме, возможно, последнего, дерево полностью заполнено. Узлы на последнем уровне заполняются слева направо. Это позволяет эффективно хранить кучу в виде массива.
• Свойство кучи:
  • Max-heap: Значение каждого узла больше или равно значениям его дочерних узлов. Максимальный элемент всегда находится в корне.
  • Min-heap: Значение каждого узла меньше или равно значениям его дочерних узлов. Минимальный элемент всегда находится в корне.

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

• Вставка элемента: Добавление нового элемента и поддержание свойства кучи.
• Удаление элемента: Удаление корневого элемента (максимального или минимального в зависимости от типа кучи) и поддержание свойства кучи.
• Создание кучи: Построение кучи из массива элементов.

Применение кучи:

• Сортировка: Алгоритм пирамидальной сортировки (Heapsort).
• Очереди с приоритетом: Эффективная реализация очередей, где элементы обрабатываются в порядке приоритета.
• Алгоритмы поиска: Например, поиск k-го по величине элемента.
• Алгоритмы на графах: Например, алгоритм Дейкстры.

Представление кучи массивом:

Поскольку куча является полным бинарным деревом, ее можно эффективно хранить в массиве без использования указателей.

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

# Пример представления min-heap в виде массива
heap_array = [10, 15, 20, 17, 25, 30]

# Корень: heap_array[0] = 10
# Левый потомок корня: heap_array[2*0 + 1] = heap_array[1] = 15
# Правый потомок корня: heap_array[2*0 + 2] = heap_array[2] = 20
# Родитель элемента по индексу 3 (17): heap_array[(3-1)//2] = heap_array[1] = 15