Построение пирамиды

Возьмем исходный массив.

44_55_12_42_94_18_06_67

Построение пирамиды начнется с элементов a[k] и a[n], где n - количество элементов в массиве, а k =n/2, так ка эта часть массива удовлетворяет свойству пирамиды (родитель больше или равен ребенку) по той причине, что эти элементы просто не имеют детей.

Далее будем расширять часть массива, обладающую свойством пирамиды. Для этого используется следующая процедура:

• начинаем двигаться от элемента k-1 до 0,
• смотрим на сыновей i-го элемента и выбираем наибольшего из них,
• если выбранный элемент больше чем a[i], то меняем его с a[i] местами, после чего опять переходим к шагу 3, рассматривая новое положение a[i]-го в массиве.

Пример построения пирамиды приведен на рисунке 1. Закрашенные элементы показывают, что данный элемент удовлетворяет правилу пирамиды.

Рисунок 1. Построение пирамиды.

Дата добавления: 2014-01-11