Теоретические сведения. Пирамида (Heap) – это структура данных, представленная в виде бинарного дерева, значения родительских узлов в котором меньше или равны

Пирамида (Heap) – это структура данных, представленная в виде бинарного дерева, значения родительских узлов в котором меньше или равны, значению любого из наследников.

В пирамидах существуют два вида упорядочения:

1. По возрастанию.

2. По убыванию.

При упорядочении по возрастанию значение родительского узла меньше или равно любому из его наследников (рис. 1).

При упорядочении по убыванию значение родительского узла больше или равно любому из его наследников (рис. 2).

Рис. 1. Пирамида, упорядоченная по возрастанию

Рис. 2. Пирамида, упорядоченная по убыванию

Пирамиду эффективней всего представить в виде одномерного массива, узлы которого имеют последовательную индексацию.

Рис. 3. Структура массива

Рис. 4. Структура массив

Для представления пирамиды в виде дерева, необходимо знать, как родительский узел связан с наследниками и как наследники связаны с родительским узлом.

Пусть i – номер родительского узла, тогда левый сын будет иметь индекс в массиве 2 i +1, а правый – 2 i +2. Индекс левого сына будет всегда нечетным, а правого – четным.

Пусть i – порядковый номер дочернего узла, тогда номер родительского узла можно найти по формуле: (.

Для левого сына всегда будет получаться целое число, а для правого сына значение необходимо округлить до наименьшего целого.

В языке C++ не нужно округлять до наименьшего целого. Это происходит автоматически при выполнении целочисленного деления.

В пирамиде используют две операции: вставка и удаление.

1. Операция вставки

Вставка очередного узла всегда осуществляется в конец пирамиды.

После этого может произойти изменение структуры «пирамида», поэтому необходимо сравнить значение вставляемого узла с родительским узлом. Если значение данного узла меньше (больше) родительского, то вставляемый узел меняют с родительским узлом местами. И т.д. поднимаясь вверх по структуре «дерево».

Данная операция рассматривается отдельно, как перемещение узла вверх до тех пор, пока не будет достигнут корень дерева или не будет найдено правильное место узла в его структуре.

2. Операция удаления

Операция удаления выполняется только для корня дерева, в котором будет всегда находиться минимальный (максимальный) элемент. После удаления корня, на его место помещают последний элемент в структуре «пирамида».

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

Пирамида является одним из самых эффективных и устойчивым методом сортировки элементов. Она является основой очередей приоритетов и используется в БД в качестве индексов.