Массив М

1

2 3

4 5 6 7

8 9 10

Рис. 5. Представление массива в виде дерева

Поиск максимального элемента массива в этом алгоритме основан на понятии пирамиды. Дерево (поддерево) является пирамидой, если каждый элемент в нем больше или равен элементам, которые являются его сыновьями. Корень пирамиды — максимальный элемент массива. Пирамида для массива M (см. таблицу 10) представлена на рис. 6.

Рис.6. Пирамида для массива М

Построив пирамиду для массива, можно, в соответствии с алгоритмом сортировки вставками, максимальный элемент, который находится в корне пирамиды (корень пирамиды — первый элемент массива), поменять местами с последним элементом массива. В результате получим массив М (см. таблицу 11) и его представление без последнего элемента в виде дерева на рис.7.

Таблица 11