Напиши полную реализацию Binary Heap на C++? Нужно всё: заголовочный файл с объявлениями класса и сигнатурами функций-членов, файл с реализацией всех методов, и тестовую программу, которая покажет, как работает этот heap — вставка элементов, удаление минимума и обработка переполнения.

Обзор

Бинарная куча — это полное бинарное дерево, которое удовлетворяет свойству кучи, где каждый родительский узел меньше своих потомков. В этой реализации используется min-heap, хранящаяся в векторе для эффективных операций приоритетной очереди.

Основная структура данных

Куча представлена с использованием векторного массива, где:

• Индекс 0 не используется (индексация начинается с 1)
• Для любого узла с индексом i его потомки находятся в 2*i и 2*i+1
• currentSize отслеживает количество элементов, которые сейчас в куче

Ключевые операции

Insert

• Добавляешь элемент в конец и просеиваешь вверх, сравнивая с родителем
• Меняешь местами с родителем, если он меньше, продолжаешь, пока свойство кучи не восстановится
• Временная сложность: O(log n)
• Выбрасывает исключение Overflow, если куча переполнена

Delete Minimum

• Удаляешь корень (наименьший элемент) и заменяешь его последним элементом
• Просеиваешь вниз замену, сравнивая с меньшим потомком
• Продолжаешь, пока свойство кучи не восстановится
• Временная сложность: O(log n)
• Выбрасывает исключение Underflow, если куча пуста

Find Minimum

• Возвращаешь элемент в корне (индекс 1)
• Временная сложность: O(1)

Вспомогательные методы

percolateDown() — перемещает элемент вниз по куче

• Сравнивает узел с обоими потомками
• Меняет местами с меньшим потомком, если он меньше текущего элемента
• Продолжает рекурсивно, пока не найдётся правильная позиция

buildHeap() — строит кучу из произвольного набора элементов

• Вызывает percolateDown() для всех нелистовых узлов
• Работает за время O(n) несмотря на повторные вызовы

Вспомогательные методы — isEmpty(), isFull(), makeEmpty() предоставляют базовые проверки состояния

Обработка ошибок

В реализации используются пользовательские исключения:

• Underflow — выбрасывается, когда операции пытаются обратиться к пустой куче
• Overflow — выбрасывается, когда вставка превышает ёмкость

Тестирование

Тестовая программа проверяет корректность, вставляя 10 000 элементов в псевдослучайном порядке, а затем проверяя, что они извлекаются в отсортированном порядке.