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

1. Вставка элемента (Insert) - \(O(\log n)\):

• Для вставки нового элемента он сначала помещается в конец кучи. Затем, чтобы сохранить свойства кучи, производится "просеивание вверх" (или "подъем"): элемент сравнивается с его родителем, и, если нарушается порядок кучи, они меняются местами. Это повторяется, пока не будет найдено правильное место для элемента или он не достигнет корня.

2. Удаление минимального/максимального элемента (Delete Min/Max) - \(O(\log n)\):

• Элемент, находящийся в конце кучи, перемещается на место корневого элемента. Затем производится "просеивание вниз", чтобы восстановить свойства кучи: новый корень сравнивается с детьми, и если порядок нарушается, он меняется местами с наименьшим (в min-heap) или наибольшим (в max-heap) ребенком. Процесс повторяется, пока не будет восстановлен порядок.

3. Поиск минимального/максимального элемента (Find Min/Max) - \(O(1)\):

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

4. Слияние двух куч (Merging two heaps) - \(O(n)\):

• Можно выполнить за линейное время относительно общего числа элементов. Обычно это делается путем простого объединения элементов двух куч и последующего построения новой кучи из получившегося списка элементов.

5. Уменьшение ключа (Decrease key) - \(O(\log n)\) для бинарной кучи:

• В куче обычно влечет за собой его "подъем" вверх по куче (если это min-heap), так как элемент становится "легче". Элемент сравнивается с родителем, и они меняются местами, если порядок кучи нарушен.

6. Увеличение ключа (Increase key) - \(O(\log n)\) для бинарной кучи:

• Аналогично уменьшению ключа, но в данном случае элемент "опускается" вниз в куче (если это min-heap), так как он становится "тяжелее".

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

May 24, 2024, easyoffer