Принцип работы алгоритма «Пирамида» для формирования числовой последовательности заключается в следующем: 2
- Из исходной неотсортированной последовательности строится структура данных — пирамида. 2 Она обладает тем свойством, что в её вершине находится максимальный элемент. 2
- Далее начинаются основные итерации сортировки. 2 На каждой итерации: 2
- вынимают вершину пирамиды; 2
- на её место вставляют последний в пирамиде элемент; 2
- «просеивают» этот элемент сквозь пирамиду. 2
- И так до последней итерации, на которой из всей пирамиды останется только вершина, которую вставляют в конец полученной отсортированной последовательности. 2
- После того как последний элемент ставят на вершину, пирамида теряет свои свойства, становится «разбалансированной». 2 Поэтому нужно этот элемент поставить в соответствующее ему место, а на вершину восстановить максимальный элемент. 2
Таким образом, принцип работы алгоритма «Пирамида» основан на построении и изменении бинарного дерева таким образом, чтобы в его корне всегда находилось максимальное значение. 4