Cout << "Heap";

Привет! Сегодня мы рассмотрим структуру данных под названием куча (англ. heap).

Что такое куча?

Помните, недавно была опубликована статья про такую структуру данных, как дерево? Так вот, куча - это двоичное дерево, в котором выполняются специальные условия. Иногда кучу также называют пирамидой.

Существуют кучи, у которых в корневом узле находится максимальный элемент (их называют max-heap) и те, у которых в корневом узле находится минимальный элемент (их называют min-heap).

Свойства кучи

Для определенности возьмем в пример max-heap. Тогда свойства звучат так:

• все слои бинарного дерева должны быть заполнены целиком, кроме, быть может, последнего;
• последний слой должен заполняться слева направо.

Числа, хранящиеся в бинарном дереве, удовлетворяют следующему условию:

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

Из последнего свойства следует, что самый первый элемент в куче всегда будет максимальным, а если рассматривать min-heap, то, соответственно, минимальным. Это важное преимущество рассматриваемой структуры данных.

Зачем использовать кучу?

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

Кучи легко реализуются через массивы, нужно лишь грамотно оперировать индексами. Об этом поговорим далее.

Как построить кучу?

Для того, чтобы построить кучу, реализуем процедуру heapify. Она нужна для того, чтобы восстанавливать свойства кучи в случае, если элементы в массиве им не удовлетворяют. Ее суть такова: нужно определить узловой элемент (node) и найти больший элемент среди него и его потомков. Если какой-то из потомков оказался больше изначального node элемента, то мы меняем их местами в массиве и повторяем ту же процедуру с начала, но уже для большего элемента, который мы нашли на предыдущей итерации. Останавливаемся мы в тот момент, когда в рассматриваемом поддереве значение обоих потомков данного узла не больше значения самого узла.

Для узлового элемента i в массиве его левого потомка можно найти, обратившись по индексу 2 * i + 1, а правого - по индексу 2 * i + 2.

Также для любого элемента i (кроме корневого) можно найти его родителя по индексу (i - 1) / 2.

Реализация алгоритма на С++ может выглядеть так:

Теперь непосредственно к формированию кучи из массива. Для этого напишем процедуру buildHeap, которая будет использовать ранее написанную процедуру heapify. Она будет запускать heapify для каждого элемента (в обратном порядке), у которого есть потомки. Последний такой элемент имеет индекс n / 2 - 1. Реализация:

Итак, мы разобрались, что куча из себя представляет, какие она имеет свойства, затронули ее использование и даже реализовали в коде. Ура!

На самом деле, этой статьи практически хватает для того, чтобы реализовать сортировку кучей. Как раз о ней мы и поговорим в ближайшем будущем :)

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

С ув. ваш TechMentor.