heapp

class MinHeap:
    def __init__(self):
        # Инициализация пустого списка для хранения элементов кучи
        self.heap = []

    def insert(self, item):
        """
        Добавляет элемент в кучу и восстанавливает её свойства.
        :param item: элемент для добавления в кучу
        """
        self.heap.append(item)             # Добавляем элемент в конец списка (в конец кучи)
        self._heapify_up(len(self.heap) - 1)  # Восстанавливаем свойства кучи, подняв элемент вверх

    def get_min(self):
        """
        Возвращает минимальный элемент (корень) кучи без его удаления.
        :return: минимальный элемент кучи
        :raises IndexError: если куча пуста
        """
        if self.is_empty():
            raise IndexError("Heap is empty")  # Бросаем исключение, если куча пуста
        return self.heap[0]                    # Минимальный элемент всегда находится в корне (первый элемент списка)

    def extract_min(self):
        """
        Удаляет и возвращает минимальный элемент (корень) кучи.
        :return: минимальный элемент кучи
        :raises IndexError: если куча пуста
        """
        if self.is_empty():
            raise IndexError("Heap is empty")  # Бросаем исключение, если куча пуста

        if self.size() == 1:
            # Если в куче один элемент, просто удаляем и возвращаем его
            return self.heap.pop()

        root = self.heap[0]                    # Сохраняем минимальный элемент для возврата
        self.heap[0] = self.heap.pop()         # Перемещаем последний элемент в корень
        self._heapify_down(0)                  # Восстанавливаем свойства кучи, спуская элемент вниз
        return root                            # Возвращаем минимальный элемент

    def size(self):
        """
        Возвращает количество элементов в куче.
        :return: размер кучи
        """
        return len(self.heap)

    def is_empty(self):
        """
        Проверяет, пуста ли куча.
        :return: True, если куча пуста, иначе False
        """
        return len(self.heap) == 0

    def _heapify_up(self, index):
        """
        Восстанавливает свойства кучи после вставки элемента, перемещая его вверх по дереву.
        :param index: индекс вставленного элемента
        """
        while index > 0:
            parent_index = (index - 1) // 2    # Вычисляем индекс родительского узла
            if self.heap[index] < self.heap[parent_index]:
                # Если текущий элемент меньше родителя, меняем их местами
                self.heap[index], self.heap[parent_index] = self.heap[parent_index], self.heap[index]
                index = parent_index           # Обновляем индекс на индекс родителя для дальнейшего подъема
            else:
                break                          # Если свойство кучи не нарушено, завершаем цикл

    def _heapify_down(self, index):
        """
        Восстанавливает свойства кучи после удаления элемента, перемещая элемент вниз по дереву.
        :param index: индекс элемента, который нужно переместить вниз
        """
        size = self.size()
        while index < size:
            smallest = index                   # Предполагаем, что текущий узел наименьший
            left_child = 2 * index + 1         # Индекс левого дочернего узла
            right_child = 2 * index + 2        # Индекс правого дочернего узла

            # Проверяем, существует ли левый дочерний узел и меньше ли он текущего наименьшего
            if left_child < size and self.heap[left_child] < self.heap[smallest]:
                smallest = left_child

            # Проверяем, существует ли правый дочерний узел и меньше ли он текущего наименьшего
            if right_child < size and self.heap[right_child] < self.heap[smallest]:
                smallest = right_child

            if smallest != index:
                # Если наименьший узел не текущий, меняем их местами и продолжаем спускаться
                self.heap[index], self.heap[smallest] = self.heap[smallest], self.heap[index]
                index = smallest               # Обновляем индекс на индекс наименьшего дочернего узла
            else:
                break                          # Если свойство кучи восстановлено, завершаем цикл

    def build_heap(self, array):
        """
        Построить кучу из заданного массива за линейное время O(n).
        :param array: список элементов для построения кучи
        """
        self.heap = array[:]                   # Копируем элементы массива в кучу
        # Начинаем с первого узла, имеющего потомков, и двигаемся вверх к корню
        for i in range(len(self.heap) // 2 - 1, -1, -1):
            self._heapify_down(i)              # Восстанавливаем свойства кучи для каждого узла

    def __str__(self):
        """
        Возвращает строковое представление элементов кучи.
        :return: строка с элементами кучи
        """
        return "Heap: " + str(self.heap)