Свойства пирамиды

1. Если последовательность a_i, a_i+1,…,а_k-1, a_k является (i, k)-пирамидой, то последовательность a_i+1,…,a_k-1, полученная усечением элементов с обоих концов последовательности, является (i+1, k-1)пирамидой.

2. Если последовательность a₁…a_n – (1, n)-пирамида, то а₁ – минимальный элемент последовательности.

3. Если a₁, a₂…,a_n/2,a_n/2+1,…a_n-произвольная последовательность, то последовательность a_n/2+1,…,a_n является (n/2+1, n)-пирамидой.

Процесс построения пирамиды выглядит следующим образом. Дана последовательность a_s+1,…,a_k, которая является (s+1, k)-пирамидой. Добавим новый элемент х и поставим его на s -тую позицию в последовательности, т.е. пирамида всегда будет расширяться влево. Если выполняется (*), то полученная последовательность – (s, k)-пирамида. Иначе найдутся элементы a_2s+1,a_2s такие, что либо a_2s < a_s либо a_2s+1 < a_s.

Пусть имеет место первый случай, второй случай рассматривается аналогично. Поменяем местами элементы a_s и a_2s. В результате получим новую последовательность a_s^’,a_s+1,…, a_2s^’,…, a_k. Повторяем все действия для элемента a_2s^’ и т.д. пока не получим (s, k)-пирамиду.

Пример. Добавим в (2, 8)-пирамиду новый элемент х=6.

Условные обозначения: Х новый элемент

Х сравнение с включаемым элементом

обмен элементов

								пирамида
6	3	2
					4	5
								пирамида

Рисунок 7 Добавление в пирамиду нового элемента