heap

class MinHeap:
    def __init__(self):
        self.heap = []

    def insert(self, item):
        """Добавить элемент в кучу и восстановить ее свойства."""
        self.heap.append(item)
        self._heapify_up(len(self.heap) - 1)

    def get_min(self):
        """Вернуть минимальный элемент (корень) кучи без удаления."""
        if self.size() > 0:
            return self.heap[0]
        return None

    def extract_min(self):
        """Удалить и вернуть минимальный элемент (корень) кучи."""
        if self.size() == 0:
            return None
        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 len(self.heap)

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

    def _heapify_up(self, index):
        """Восстановить свойства кучи после вставки элемента."""
        parent_index = (index - 1) // 2
        if index > 0 and self.heap[index] < self.heap[parent_index]:
            # Поменять местами с родителем и рекурсивно подняться
            self.heap[index], self.heap[parent_index] = self.heap[parent_index], self.heap[index]
            self._heapify_up(parent_index)

    def _heapify_down(self, index):
        """Восстановить свойства кучи после удаления элемента."""
        smallest = index
        left_child = 2 * index + 1
        right_child = 2 * index + 2

        if left_child < self.size() and self.heap[left_child] < self.heap[smallest]:
            smallest = left_child
        if right_child < self.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]
            self._heapify_down(smallest)

    def __str__(self):
        """Отобразить элементы кучи."""
        return "Heap: " + str(self.heap)