1. Если последовательность ai, ai+1,…,аk-1, ak является (i, k)-пирамидой, то последовательность ai+1,…,ak-1, полученная усечением элементов с обоих концов последовательности, является (i+1, k-1)пирамидой.
2. Если последовательность a1…an – (1, n)-пирамида, то а1 – минимальный элемент последовательности.
3. Если a1, a2…,an/2,an/2+1,…an-произвольная последовательность, то последовательность an/2+1,…,an является (n/2+1, n)-пирамидой.
Процесс построения пирамиды выглядит следующим образом. Дана последовательность as+1,…,ak, которая является (s+1, k)-пирамидой. Добавим новый элемент х и поставим его на s -тую позицию в последовательности, т.е. пирамида всегда будет расширяться влево. Если выполняется (*), то полученная последовательность – (s, k)-пирамида. Иначе найдутся элементы a2s+1,a2s такие, что либо a2s < as либо a2s+1 < as.
Пусть имеет место первый случай, второй случай рассматривается аналогично. Поменяем местами элементы as и a2s. В результате получим новую последовательность as’,as+1,…, a2s’,…, ak. Повторяем все действия для элемента a2s’ и т.д. пока не получим (s, k)-пирамиду.
Пример. Добавим в (2, 8)-пирамиду новый элемент х=6.
Условные обозначения: Х новый элемент
Х сравнение с включаемым элементом
обмен элементов
пирамида | ||||||||
6 | 3 | 2 | ||||||
4 | 5 | |||||||
пирамида |
Рисунок 7 Добавление в пирамиду нового элемента