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

Куча (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).
• Реализация алгоритмов на графах (например, алгоритм Дейкстры).

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

# Реализация кучи минимума
class MinHeap:
    def __init__(self):
        self.heap = []

    def parent(self, i):
        return (i - 1) // 2

    def left(self, i):
        return 2 * i + 1

    def right(self, i):
        return 2 * i + 2

    def insert(self, key):
        self.heap.append(key)
        i = len(self.heap) - 1
        # Всплываем элемент, пока не нарушено свойство кучи
        while i > 0 and self.heap[self.parent(i)] > self.heap[i]:
            self.heap[i], self.heap[self.parent(i)] = self.heap[self.parent(i)], self.heap[i]
            i = self.parent(i)

    def extract_min(self):
        if len(self.heap) == 0:
            return None
        if len(self.heap) == 1:
            return self.heap.pop()

        root = self.heap[0]
        self.heap[0] = self.heap.pop() # Заменяем корень последним элементом
        self.heapify(0) # Опускаем новый корень

        return root

    def heapify(self, i):
        l = self.left(i)
        r = self.right(i)
        smallest = i

        # Находим наименьший элемент среди корня и его потомков
        if l < len(self.heap) and self.heap[l] < self.heap[smallest]:
            smallest = l
        if r < len(self.heap) and self.heap[r] < self.heap[smallest]:
            smallest = r

        # Если наименьший не корень, меняем их местами и продолжаем опускать
        if smallest != i:
            self.heap[i], self.heap[smallest] = self.heap[smallest], self.heap[i]
            self.heapify(smallest) # Рекурсивный вызов для смещенного элемента

Куча является эффективной структурой для операций с приоритетами благодаря логарифмической временной сложности основных операций.